精华内容
下载资源
问答
  • 谷歌完成一次搜索请求,时间不足一秒、平均往返距离却要约2400公里。每时每刻谷歌都有200多项改进算法的在线实验,一个想法要通过多道考验才能付诸执行。而在个性化搜索日益重要的今天,谷歌算法改进也面临着新的...

    谷歌完成一次搜索请求,时间不足一秒、平均往返距离却要约2400公里。每时每刻谷歌都有200多项改进算法的在线实验,一个想法要通过多道考验才能付诸执行。而在个性化搜索日益重要的今天,谷歌算法改进也面临着新的挑战。

    来自官方的数据显示,从2003年到现在谷歌搜索已经接受超过4500亿个搜索请求。而用户每天发出的搜索请求中,有16-20%是全新的关键词。

    一个基本的搜索过程分这样几步:提交搜索请求->发送->筛选分类->查找索引->选择网页->结果排名->结现结果。谷歌给出的解释说,一个请求会被分发到数千个数据中心,然后根据关键词进行匹配,再根据数百个指标对得到的数据进行排名。

    完成一次搜索的基本流程(图片由谷歌提供)
    完成一次搜索的基本流程(图片由谷歌提供)

    这个复杂的过程通常在一秒内完成,但平均每个谷歌搜索的关键词往返于用户电脑和数据中心的距离约为2400公里(1500英里)。

    “很多人认为谷歌已经解决了搜索的问题,但是在谷歌看来搜索的发展才刚刚起步。如果说搜索是一本书,那谷歌才刚写完了开篇”,谷歌工程总监斯考特-霍夫曼(Scott Huffman)在谈到搜索时说,十多年来谷歌搜索的算法一直在不断改进。

    每年谷歌搜索结果都会改变20-30%左右。霍夫曼的主要工作之一,就是对谷歌搜索质量进行评估,在他看来这个过程远比外界看到的复杂。

    以去年为例,在众多的搜索算法改进构思中,有41831项进行了必要性评估,这其中又有9250项进行了小规模实验,进而又有7363项进行了在线实验,最终有520多项改进被付诸实施。霍夫曼总结谷歌改进算法的方式为:数据驱动、实验评估。

    谷歌搜索平均每时每刻都有200多项实验在进行;而在评估的过程中,既会借助基于统计学搭建的模型,还依靠多种语言的独立评估员。

    霍夫曼表示谷歌搜索算法近期的主要改进,可以归纳为三个方面。

    新鲜度算法调整:在某些情况下,谷歌需要为用户提供最新搜索结果,比如即时新闻、定期发生的重大事件以及内容频繁更新的话题等。如果搜索“奥运会”,用户会得到与即将举办的伦敦奥运会相关的最新搜索结果,而非关于1984年奥运会的陈旧信息。

    优质网站算法调整:这对包含原始信息、研究调查、深度报道、精准分析等内容的高质量网站十分有利,提高了它们在搜索结果中的排名。

    页面布局算法调整:这一改进关注用户在点击搜索结果后所看到的网页布局,提升网页信息的丰富程度 ,提高信息容易被搜索到的网页的排名。

    除此以外,谷歌还计划将更多社交、移动、位置等信息元素,更好的与搜索进行整合。这一方面会让搜索结果更加的个性化,但同时也给谷歌带来新的难题:如何衡量并提升越来越个性化的搜索结果。此前的实验方式必须有所调整。

    霍夫曼对此解释说,对于受个性化影响较大的因素,谷歌会采用更多的在线实验方式进行考察。例如考察一个用户的跳转和停留时间,通过统计模型对相关数据进行分析、判断。此外,还会在得到允许的情况下获取评估员的个人信息,并据此改进搜索结果。

    “新的算法改进想法往往是在解决问题时产生的”,霍夫曼说,目前谷歌在搜索算法开发上投入的时间,已经超过1000人工年。

    展开全文
  • 关键字:UDP,TCP,服务器,Java,RTT,往返时间,中位数,标准差,算术平均值 ==================== Java客户端-服务器程序对。 服务器等待传入的UDP或TCP数据包,然后将答复发送回发送方。 客户端向服务器发送一...
  • 往返时间的估计与超时   TCP采用超时/重传机制来处理报文段的丢失问题。尽管这在概念上面很简单,但是在实际中还是会产生很多微妙的问题。最明显还是超时时间间隔的设置。很显然,这个时间间隔肯定会大于RTT时间,...

    往返时间的估计与超时

      TCP采用超时/重传机制来处理报文段的丢失问题。尽管这在概念上面很简单,但是在实际中还
    是会产生很多微妙的问题。最明显还是超时时间间隔的设置。很显然,这个时间间隔肯定会大于RTT
    时间,但是具体为多大呢?如何估计最开始的往返时间呢?下面将介绍这些问题的一些解决办法。

    估计往返时间

      报文段的样本RTT(表示为SampleRTT)为某报文段发出到对该报文段的确认被收到之间的时间
    量大多数TCP的实现仅在某个时刻做一次SampleRTT测量,而不是为每个报文段测量一个SampleRTT。
      也就是说,在任何时刻,仅为一个已发送但是目前尚未被确认的报文段估计SampleRTT,从而产生
    一个接近每个RTT的新SampleRTT值。

      另外,TCP绝不为被重传的报文计算SampleRTT;它仅为传输一次的报文段测量SampleRTT。

      由于路由器的拥塞和端系统负载的变化,这些报文段的SampleRTT是波动的,所以给定的任何
    SampleRTT都是非典型的。因此要取得典型的RTT,就要对SampleRTT进行加权取值。

            EstimatedRTT = (1-α)*EstimatedRTT + α*SampleRTT

      [RFC 6298]中给出α的参考值为0.125
      对于最近的样本赋予较大的权值,是因为越近的样本越能反应网络当前的拥塞状况。
      从统计学观点讲,这种平均被称为指数加权移动平均(EWMA)

      除估算RTT外,测量RTT变化也是很有用的!
      [RFC 6298]定义了RTT偏差 DevRTT,用于估算SampleRTT偏离EstimatedRTT的程度:

           DevRTT = (1-β)*DevRTT + β*|SampleRTT - EstimatedRTT|

      DevRTT是SampleRTT和EstimatedRTT之差的指数加权移动平均
      如果SampleRTT的波动小那么DevRTT的波动便会小,反之亦此。
      第一次的DevRTT=1/2(SampleRTT),以后按公式来计算,推荐β为0.25

    设置和管理重传超时间隔

      超时时间间隔应该大于EstimatedRTT并且不能大于太多。超时时间间隔为EstimatedRTT加
    上一些余量。并且在SampleRTT值波动大时,余量较大;当波动较小时,余量较小。因此就用
    到了DevRTT。由此得出TCP重传时间间隔计算公式:

          TimeoutInterval = EstimatedRTT + 4*DevRTT

      推荐的初始TimeoutInterval为1秒。
      出现超时后,TimeoutInterval直接加倍
      因为此次重传可能是报文确认ACK因为网络拥塞而延迟到达从而导致报文重传,重传报文
    后,不久,ACK到达,会导致SampleRTT变小,进而使TimeoutInterval变小,使后面的报文出
    现过早超时!

      一旦报文段收到并更新EstimatedRTT后,TimeoutInterval又使用上述公式。


      此文为《计算机网络 自顶向下方法》的学习笔记4

    转载于:https://www.cnblogs.com/myworld7/p/8372456.html

    展开全文
  • 21.3 往返时间测量 T C P超时与重传中最重要的部分就是对一个给定连接的往返时间( RT T)的测量。由于路由器和网络流量均会变化,因此我们认为这个时间可能经常会发生变化, T C P应该跟踪这些变化并相应地改变其...

    第21章 TCP的超时与重传

    21.3 往返时间测量

    T C P超时与重传中最重要的部分就是对一个给定连接的往返时间( RT T)的测量。由于路由器和网络流量均会变化,因此我们认为这个时间可能经常会发生变化, T C P应该跟踪这些变化并相应地改变其超时时间。

    首先T C P必须测量在发送一个带有特别序号的字节和接收到包含该字节的确认之间的RT T。在上一章中,我们曾提到在数据报文段和 A C K之间通常并没有一一对应的关系。在图2 0 . 1中,这意味着发送方可以测量到的一个 RT T,是在发送报文段4(第1 ~ 1 0 2 4字节)和接收报文段7(对1 ~ 1 0 2 4字节的A C K)之间的时间,用M表示所测量到的RT T。最初的T C P规范使T C P使用低通过滤器来更新一个被平滑的 RT T估计器(记为O)。 R← R+ ( 1- )M这里的是一个推荐值为 0 . 9的平滑因子。每次进行新测量的时候,这个被平滑的 RT T将得到更新。每个新估计的9 0%来自前一个估计,而1 0 %则取自新的测量。

    该算法在给定这个随RT T的变化而变化的平滑因子的条件下, RFC 793推荐的重传超时时间RTO(Retransmission Ti m e O u t)的值应该设置为

    RTO = R
    

    这里的 是一个推荐值为2的时延离散因子。[Jacobson 1988] 详细分析了在 RT T变化范围很大时,使用这个方法无法跟上这种变化,从而引起不必要的重传。正如 J a c o b s o n记述的那样,当网络已经处于饱和状态时,不必要的重传会增加网络的负载,对网络而言这就像在火上浇油一样。

    除了被平滑的RT T估计器,所需要做的还有跟踪RT T的方差。在往返时间变化起伏很大时,基于均值和方差来计算 RTO,将比作为均值的常数倍数来计算 RTO能提供更好的响应。在[Jacobson 1988]中的图5和图6中显示了根据RFC 793计算的某些实际往返时间的 RTO和下面考虑了往返时间的方差所计算的 RTO的比较结果。

    正如J a c o b s o n所描述的,均值偏差是对标准偏差的一种好的逼近,但却更容易进行计算(计算标准偏差需要一个平方根)。这就引出了下面用于每个 RT T测量M的公式。

    E rr = M-A A←A + g E rr D←D + h( | E rr |-D)
    RTO = A + 4D
    

    这里的A是被平滑的RT T(均值的估计器)而D则是被平滑的均值偏差。 E rr是刚得到的测量结果与当前的RT T估计器之差。A和D均被用于计算下一个重传时间( RTO)。增量g起平均作用,取为1 / 8(0 . 1 2 5)。偏差的增益是h,取值为0 . 2 5。当RT T变化时,较大的偏差增益将使 RTO快速上升。

    [Jacobson 1988]指明在计算 RTO时使用 2 D,但经过后来更深入的研究,[Jacobson1990c]将该值改为4D,也就是在BSD Net/1的实现中使用的那样。

    J a c o b s o n指明了一种使用整数运算来计算这些公式的方法,并被许多实现所采用(这也就是g, h和倍数4均是2的乘方的一个原因,这样一来计算均可只通过移位操作而不需要乘、除运算来完成)。 将J a c o b s o n与最初的方法比较,我们发现被平滑的均值计算公式是类似的( 是1减去增益g),而增益可使用不同的值。而且 J a c o b s o n计算RTO的公式依赖于被平滑的 RT T和被平滑的均值偏差,而最初的方法则使用了被平滑的 RT T的一个倍数。在看完下一节中的例子时,我们将看到这些估计器是如何被初始化的。

    Karn算法
    在一个分组重传时会产生这样一个问题:假定一个分组被发送。当超时发生时, RTO正如2 1 . 2节中显示的那样进行退避,分组以更长的 RTO进行重传,然后收到一个确认。那么这个A C K是针对第一个分组的还是针对第二个分组呢?这就是所谓的重传多义性问题。

    [Karn and Partridge 1987]规定,当一个超时和重传发生时,在重传数据的确认最后到达之前,不能更新 RT T估计器,因为我们并不知道 A C K对应哪次传输(也许第一次传输被延迟而并没有被丢弃,也有可能第一次传输的 A C K被延迟)。

    并且,由于数据被重传, RTO已经得到了一个指数退避,我们在下一次传输时使用这个退避后的 RTO。对一个没有被重传的报文段而言,除非收到了一个确认,否则不要计算新的RTO。

    展开全文
  • RTT Round-Trip Time 比如重传定时器,那么到底多长时间没接到ACK才重传呢? 测量的RTT RTT的测量可以采用两种方法: (1)重传队列中数据包的TCP控制块在TCP重传队列中保存着发送而未被确认的数据包,数据包skb中的...

    RTT Round-Trip Time

    比如重传定时器,那么到底多长时间没接到ACK才重传呢?

     

    测量的RTT

    RTT的测量可以采用两种方法:

    (1)重传队列中数据包的TCP控制块
    在TCP重传队列中保存着发送而未被确认的数据包,数据包skb中的TCP控制块包含着一个变量,
    tcp_skb_cb->when,记录了该数据包的第一次发送时间。
    RTT = 当前时间 – when

    image

     

     

    (2)TCP Timestamp选项
    在前面的blog中有详细的介绍过这个选项,TCP时间戳选项可以用来精确的测量RTT。
    RTT = 当前时间 -  数据包中Timestamp选项的回显时间
    这个回显时间是该数据包发出去的时间,知道了数据包的接收时间(当前时间)和发送时间
    (回显时间),就可以轻松的得到RTT的一个测量值。

     

    为什么用时间戳选项测量RTT?

    既然不用时间戳选项就可以实现RTT测量,为何还增加时间戳选项呢?看下面解释:

    “TCP must use Karn's algorithm for taking RTT samples. That is, RTT samples MUST NOT be made using segments that were retransmitted (and thus for which it is ambiguious whether the reply was for the first instance of the packet or a later instance). The only case when TCP can safely take RTT samples from retransmitted segments is when the TCP timestamp option is employed, since the timestamp option removes the ambiguity regarding which instance of the data segment triggered the acknowledgement.”

    上面这段话的意思是,不能确定ACK是对原包的回复还是对重传包的回复。

    画个图就明白了,如下

    image

     

     

    平滑的RTT

    (Smoothed RTT): 因为RTT对不同的往返有不同的数值,而且其起伏比较大,以致不能为重传超时做标准,所以需要平滑的RTT,记为SRTT它对和前一个SRTT加权平均。
    即SRTT=αSRTT+(1-α)*MRTT  α推荐为0.9.
     
     

    转载于:https://www.cnblogs.com/helloweworld/archive/2013/04/21/3034019.html

    展开全文
  • 一种使用不同方法测量TCP连接的往返时间和带宽的工具。 带宽(或更准确地说,Goodput)是用谐波平均值测量的。 rtt是通过加权移动平均值来衡量的。 当前,tcp-metrics仅支持可通过HTTP / 1.1使用的资源。 原因是...
  • TCP往返传输时间(RTT)的估计

    千次阅读 2011-03-20 14:21:37
    TCP往返传输时间(RTT)的估计1) TCP传输往返时间是指发送端从发送TCP包开始到接收到它的立即响应所耗费的传输时间.当接收端和发送端同时支持TCP时戳选项时,发送端记录在TCP包头选项内的时戳可以被接收端随响应反射...
  • 时延(delay或latency)是指数据(报文、分组、比特)从网络(或链路)的一端传送到另一端所需的时间。 2.时延的组成?? 总时延 = 发送时延 + 传播时延 + 处理时延 + 排队时延 发送时延(传输时延) 从发送数据帧...
  • python从SUMO中获取车辆平均行驶时间

    千次阅读 热门讨论 2015-12-03 15:36:32
    为了计算车辆的平均行驶时间,其实就是提取出每一个车辆记录中的duration属性,然后相加取平均。 2.python代码 # -*- coding: utf-8 -*- """ Created on Thu Dec 03 18:50:50 2015 @author: Luyixiao """ ...
  • TCP超时重传时间的选择 假设往返时间是RTT0,那么若小于超时重传时间RTO,则会造成不必要的重传。假若大于RTO,则会使得网络浪费太多空间,所以综上所...但是我们可以利用每次测量得到的RTT样本,计算加权平均往返时间
  • 超时重传时间的选择RTT : 报文段的往返时间RTTS : 加权平均往返时间,也称平滑的往返时间 第一次测量到RTT样本时,RTTS 值就取该样本 此后按下列式子进行计算 新的RTTS = (1 - α) * (旧的RTTS) + α * (新的RTT...
  • 平均

    2016-10-14 21:26:03
    前段时间,媒体一直在说国家统计局发布的我国2009年住房价格平均增长1.5%,这与我们老百姓大多数人的直觉违背。 正好有个毕业的学生在媒体是记者希望谈谈统计局发布的统计数字的理解!当然,沈老师不想去挑战什么...
  • 现有的互联网以数据包传输为基础,任何一个数据包的丢失或出错都必须重新发送,而平均一个重传过程需要3秒钟,从而导致延迟。并且现有的HTTP协议也有 诱发延迟的因素,据调查,完整下载一个网页,需要在用户和服务器...
  • 郑州大学计算机网络

    2021-01-07 19:56:42
    往返时间RTT只对运输层的TCP协议才很重要,因为TCP要根据平均往返时间RTT的值来设置超时计时器的超时时间 超时重传是指只要超过了一段时间仍然没有收到确认,就重传前面发送过的分组(认为刚才发送的分组丢失了)。...
  • Java:各种协议

    2021-03-25 19:28:24
    tcp协议 RTTs 加权平均往返时间 TCP拥塞控制 进程间通信 管道 套接字 共享内存 消息队列
  • 访问网站的过程是通过建立在TCP/IP协议之上的HTTP协议来完成的。... 往返时间是指客户端等待每次请求的响应时间,平均往返时间取决于三个方面: 1. 网站服务器的延时 网站服务器造成的延时在往返...
  • 超时计时器设置

    2018-06-17 15:52:08
    TCP 保留了 RTT 的一个加权平均往返时间 RTTS(这又称为平滑的往返时间)。 第一次测量到 RTT 样本时,RTTS 值就取为所测量到的 RTT 样本值。以后每测量到一个新的 RTT 样本,就按下式重新计算一次 RTTS: 新的...
  • TCP 的重传机制

    2019-04-14 19:45:42
    重传事件 引起 TCP 对报文进行重传的事件 ...重传时间(RTO)由一个加权平均往返时间(RRTs)和 往返时间(RTT)的偏差的加权平均值(RTTD)决定 RTO=RTTS+4∗RTTDRTO = RTT_S + 4*RTT_DRTO=RTTS​+...
  • 一个报文段从发送再到接收到确认所经过的时间称为往返时间 RTT,加权平均往返时间 RTTs 计算如下: 其中,0 ≤ a ,RTTs 随着 a 的增加更容易受到 RTT 的影响。 超时时间 RTO 应该略大于 RTTs,TCP 使用的超时...
  • 网络——TCP

    2019-08-30 16:48:18
    RTTs(加权平均往返时间) 第一次测量到RTT样本时,RTTs就取所测量到的RTT样本值 新的RTTs = (1 - a)*(旧的RTTs) + a*(新的RTT样本) a 一般取0.125 RTO超市重传时间 RTO = RTTs + 4*RTTd RTTd 是RTT的...
  • SSD8-TCP-VS-UDP-java源码

    2015-05-24 09:21:23
    然后,客户端停止计时器,并计算发送包含一个字节数据的UDP包平均往返时间。因为UDP是不可靠的,可能出现丢包现象,所以需要设定一个最大接收时间。如果一个数据包丢失,则重新发送该数据包,并且不对此进行重复计数...
  • 【计算机网络】超时计时器设置

    千次阅读 2018-05-31 20:05:33
    题目描述 运输层的超时计时器的超时重传时间应设置为多大呢? 如果把超时重传时间设置得太短,就会引起很多报文段的不必要的重传,使网络负荷增大。...  TCP 保留了 RTT 的一个加权平均往返时间 R...
  • TCP超时重传

    2016-09-07 11:21:25
    什么是超时重传 往返时间RRT和超时重传时间RTO 新的平均往返时间RTO的计算 RTTnew=αRTTold+(1−α)RTT新样本RTT_{new}={\alpha}RTT_{old}+(1-\alpha)RTT_{新样本} 此处α\alpha称为平滑因子,通常α=0.9\alpha=...
  • 5.3.4 TCP可靠传输

    2020-07-03 20:56:37
    TCP可靠传输 可靠:按序收到 序号:字节编成一个序号,报文段(几个字节段) ...TCP采用自适应算法,RTTS加权平均往返时间 冗余确认(冗余ACK) 如果3个一样的冗余ACK,就会发送ACK报文,快速重传 ...
  • 可靠传输 1. 自动重传请求ARQ(Automatic Repeat reQuest): ...超时计时器 未收到确认就重传 重传时间大于平均往返时间(TTL) 操作: 收到确认后再转发下一个分组 场景 :确认丢失 确认迟到 ...
  • TCP可靠传输及流量控制实现原理 ... 超时计时器的重传时间应当比数据在分组传输的平均往返时间更长一些。  出现差错或丢失的时候,发送方会将自己备份的副本再重传一次,直到收到接收的确认信息。当接收方...
  • 超时重传(超时时间主要为加权平均往返时间) 选择确认 TCP流量控制: 利用滑动窗口实现流量控制 考虑传输效率(最大报文段长度MSS,只要达到MSS就发送报文) TCP拥塞控制: 慢开始:由...
  • TCP可靠传输 由于网络层提供尽最大努力交付,是不可靠传输,所以传输层应尽量保证实现可靠传输。 可靠传输:保证接收方进程从缓存区读出的字节流与发送方...TCP采用自适应算法,动态改变重传时间RTTs(加权平均往返时间
  • 小学奥数平均数经典问题汇总

    万次阅读 2017-09-08 16:33:07
    小学奥数平均数经典问题汇总,掌握这些平均数问题,小学奥数考试拿高分不是梦!

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,971
精华内容 4,788
关键字:

平均往返时间