logo资料库

洋葱路由算法改进（论文翻译）.pdf

发布时间：2022-06-10 发布人：admin 分类：说明书 资料大小：0.41M 资料格式：pdf 举报 版权申诉
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
资料共7页，全文预览结束
    An improved algorithm for tor circuit scheduling 本⽂文出⾃自CCS2010，是⼀一篇有关提⾼高洋葱路由⽹网络传输性能的⽂文章。洋葱路由是⼀一个著 名的匿名⽹网络，它能够帮助⽤用户隐藏发送者和接受者之间建⽴立的连接。洋葱路由在早前有很 多性能上的问题，本⽂文着眼于延迟问题，提出了⼀一个针对单个路由改进的调度算法，来减少 整个⽹网络的延迟。 1.背景介绍 洋葱路由⽹网络（The Onion Routing）是⼀一种分布式匿名⽹网络，它是靠⼀一系列的洋葱路由 器（ORs）连接起来的。传统⽹网络中⽆无法保证隐藏发信⼈人信息和收件⼈人信息，但是洋葱路由 ⽹网络可以做到。洋葱⽹网络中每⼀一个路由器接收到数据包时，只知道是谁发给⾃自⼰己的和⾃自⼰己要 发给谁，⽽而⽆无法知道源头和终点是那⾥里。洋葱路由⽹网络通过这样的⽅方式实现匿名。 洋葱路由在⼯工作的时候，需要ORs将⾃自⼰己的相关信息及时的“汇报”给⼀一个中央服务器 （Authority Directory），这个这个中央服务器会实时更新整个洋葱⽹网络的状况，并发布给需 要使⽤用信息的路由器节点。这样可以保证整个⽹网络的实时性和⼀一致性。 每⼀一个终端⽤用户要使⽤用洋葱路由⽹网络时，需要建⽴立⼀一个洋葱代理（Onion Policy）。⽤用 户使⽤用代理OP来建⽴立⼀一个传输路径，在选择路由器的时候，代理会根据获得的信息选择路 由器（⼀一般会根据带宽等性能选择）。在整个⽹网络中，每⼀一个路由器只知道⾃自⼰己的上⾏行路由 器（传递给它包的路由器）和下⾏行路由器（要接受它转发的包的路由器）是谁，因⽽而可以保 证⽹网络的匿名性。 在2008年前后，洋葱路由⽹网络的使⽤用规模正在变⼤大。在2007年的时候，全世界⼤大约分布 有1500个ORs，使⽤用者⼤大致有25万⼈人。这些路由节点都是志愿性的提供的。然⽽而2010年左右 的时候洋葱路由的发展似乎遇到瓶颈，使⽤用规模⼤大致保持稳定，没有进⼀一步的增加。这篇⽂文 章认为，是洋葱路由的性能问题导致这个结果。 洋葱路由的性能是由多⽅方⾯面因素决定的。其中最重要的原因，也是本⽂文研究的重点，就 是当多个传输路径共享⼀一个通道（Connection，指两个路由器之间建⽴立的通路）的时候，现 有的调度算法会使得⼀一些即时性较强的数据延迟增⼤大。例如我们对⽹网页上的登录操作的延迟 更加敏感，⽽而对电影下载的延迟更能容忍，如果因为电影下载⽽而影响⽹网页上的登陆，⽤用户是 难以接受的。 2.问题说明 在了解问题之前，需要先讲洋葱路由的具体⼯工作情况介绍清楚。 /1 7
    ⽤用户在客户端请求使⽤用洋葱⽹网络并建⽴立OP，接着OP会从中央服务器上获得⽹网络中的数 据，并根据节点的带宽等性能选择合适的路由器建⽴立传输路径。整个⽹网络中数据转发时，都 是固定512B⼤大⼩小的数据包（cells）。每⼀一个数据包都包括头信息和传输内容。 当⼀一个数据包到达⼀一个路由器时，路由器会进⾏行⼀一下操作。OR先处理数据包的头信息， 并从中提取需要的信息。然后将数据包放⼊入相应传输路径的转发队列中。上述过程的延迟是 很⼩小的，对于整个过程可以忽略不计。最后，需要OR选择转发队列中的数据包移动到转发 缓存（buffer）中来进⾏行数据发送。在这⼀一步中，当转发缓存中有空间时，OR会按照先后顺 序转发不同传输路径上的数据。由于这⾥里的顺序是先后顺序，那么如果有较⼤大的数据（bulk） 在队列前⾯面，⼀一定会使得即时性（bursty）的传输路径被阻碍。 根据实际⽹网络中测试数据，可以根据传输路径的数量，⽤用户数量和路由器数量判断出在 整个⽹网络中存在很多共享连接的情况。尤其是整个⽹网络中存在很多⾼高性能的节点，它们被选 择当做传输路径上的节点的可能性更⾼高。 2008年整个洋葱路由⽹网络中的统计数据如下：92.45%的链接是HTTP的，传输量占到 57.97%，SSL的链接有4.06%，传输量占到1.55%，⽐比特流(BitTorrent)的链接有3.33%，但是数 据传输量却占到40.2%。根据以上数据可以看出，较⼤大的⽐比特流传输占⽤用了整个⽹网络的很⼤大 带宽，⼀一些即时性包的传输受到了很⼤大的阻碍。 3.解决办法 要解决上⼀一部分说明的问题，作者提出了⼀一种改变传输路径优先级的算法。 作者将⽹网络中传输的数据分成两⼤大类。⼀一类是有交互的数组，例如⽹网页的访问信息，登 陆信息；另⼀一类是没有交互的数据，例如下载的电影。有交互的包都是即时性强的包，延迟 会对⽤用户体验产⽣生很⼤大的影响；没有交互的包对即时性要求⽐比较低，例如下载电影，如果延 迟多了⼏几分钟，那么对⽤用户的影响⽐比较⼩小。 最直观的办法是来区分传输的包到底属于哪⼀一类数据。如果检测出来是交互的数据，那 么提⾼高优先级就好，如果是⾮非交互的数据，那么降低优先级就好。然⽽而，事实上很难直接分 辨数据是什么数据，如果打开数据包进⾏行判断，那么会存在安全⽅方⾯面的问题。 除了⼤大⼩小的区别，两类数据还有猝发性和持久性的区别。对于需要交互的数据，⼤大⼩小⽐比 较⼩小，⽽而且数据包的传输⽐比较随机（⼈人的操作随机），所以这些传输路径上传输的数据量总 体上⽐比较少，会在短时间内发送完毕；⽽而不需要交互的数据，例如下载，持续时间⽐比较长， 所以传输⽐比较持久，传输路径上的数据包的数量⼀一直⽐比较⼤大。 这篇⽂文章期望可以找到⼀一种标准来判断每⼀一个传输路径上近期内发送的数据包。这个标 准给出的参数要能够判断⼀一段时间内某⼀一个传输路径上的数据包数量，也能随着时间变化⽽而 消逝（当这个传输路径上数据包变化时，这个标准也能实时变化）。 /2 7
    最后，作者选取了指数加权移动平均值（EWMA）的办法来衡量每⼀一个传输路径的情况。 指数加权移动平均值是⼀一个处理时间序列的常⽤用办法，它可以实时变化数据。它的某⼀一时刻 的数值是依据此时的观察值和前⼀一时间对这⼀一时间的预测值综合决定的。 作者⾸首先给每⼀一个传输通道设定⼀一个包计数器，之后的每⼀一次值都是通过EWMA来计算。 每⼀一次EWMA的值的计算都和最近⼀一段时间这个传输路径的数据流量有关系。那些被延迟的 ⼤大的数据的传输性能只有微乎其微的影响，这⼀一点可以通过作者后⾯面的实验证明。在计算过 程中，作者设定了⼀一个参数H来区分两类数据，具体的公式见原⽂文，这⾥里就不再具体说明。 同时，作者将参数H设置为路由器的参数，节点的拥有者可以认为的设置参数的值，甚⾄至关 闭有优先级的调度算法。 图1 在PLANELAB上搭建的简单⽹网络. 4.实验与结果 4.1在实验环境下的测量 图2 实验⼀一的结果，在实验环境中有优先级和没有优先级的情况下包的传输时间 作者先选择了PlaneLab进⾏行实验。这是⼀一个类似于Tor⽹网络的分布式⽹网络。典型的Tor⽹网 络⼀一般包含三个节点，这⾥里作者选⽤用了五个节点，其中两个节点来当做中央服务器。 实验⼀一设计的是⼀一个测试⼩小⽂文件传输时间的实验。作者⽤用这个实验来模拟简单的⽹网络请 求。在实验过程中，作者选择了⼤大⼩小为300KB的⽂文件进⾏行传输。在传输前也在出⼜⼝口OR上备 份⽂文件，来检查⽂文件的⼀一致性。 /3 7
    如图1所⽰示，作者设计了三个本地客户端，建⽴立了三个洋葱代理（OP）。其中两个客户 端传输的是⼤大数据块。这⾥里参数H设置为66，意味着时间没流逝66秒，原来的计数器值就会 降低50%。作者在有优先级和没有优先级的情况下分别试验了100次，结果如图2.其中横坐标 代表平均⽤用时，纵坐标是百分⽐比的累计值。从图上可以看出，在存在优先级的情况下，时延 明显要⼩小很多。 实验⼆二是在对客户端上进⾏行的实验，过程与实验⼀一较为类似，这⾥里不作具体说明。 实验三来监视具体的数据包的⽣生命历程。主要来考察⼀一个包在每⼀一个阶段到底会耗费多 少时间，以此来判断可以在哪些地⽅方进⾏行提升。 （a） （b） 图3 实验三的结果，数据包不同时间节点的情况 当⼀一个数据包到达⼀一个OR的时候，它会经历以下具体的过程。这个数据包先到到这条 传输路径的等待队列，然后等待着路由器将它移动到转发缓存（buffer）中。这个过程中的 测试设置和实验⼀一中的情况很类似。⽂文章中利⽤用libspa去记录和数据包有关的时间节点：数 据包进⼊入传输路径的等待队列的时间，从队列被移动到转发缓存的时间和离开转发缓存的时 间。⽂文中重点研究了中间节点的相关时间。图3中a和b记录了有优先级和没有优先级两种情 况下的情况。 图4 数据包在传输路径中等待的时间 /4 7
    图3中横坐标是数据包到达等待队列的时间，纵坐标是数据包进⼊入传输路径的等待队列 的时间，从队列被移动到转发缓存的时间和离开转发缓存的时间，可以看出来，在没有优先 级的情况下，⼀一个数据包把多数时间花费在队列的等待中，⽽而有优先的情况下可以⼤大⼤大减少 这个时间。平均花费的时间从原来的653毫秒降低到115毫秒。在有很多数据包在OR中排队 的时候，延迟会变得明显，那么⽤用这个办法提升的效果也会更明显。图4中展现了数据包在 传输路径中等待的时间。 4.2在实际洋葱路由⽹网络中的测量 作者⾸首先在实际的洋葱路由⽹网络中对⼩小数据的下载进⾏行了测量，实验结果如图5. 可以看出，在实际⽹网络中⼩小⽂文件下载的时间，有优先的情况⽐比没有优先的情况要好。这 图5 实际⽹网络中⼩小⽂文件的下载情况 个结果和作者在实验环境下得到的结果⼀一致。 作者在对实际⽹网络测量的时候，还得到了⼀一个有趣的结果。作者发现每天下午的延迟要 ⽐比晚上的延迟⼩小，因⽽而可以得出结论，另⼀一个半球使⽤用Tor⽹网络的⼈人更多。 图6 实际洋葱路由⽹网络中算法对⼤大数据流的影响 /5 7
    接着，作者探究了此算法对⼤大⼤大数据流传输的影响。作者认为这篇⽂文章提出的算法不可 能使得⼤大数据流的传输有太⼤大的影响。根据排队论理论中的title’s law，这个算法只是改变数 据包的传输顺序，并没有改变队列长度和包的到达率，所以平均等待时间并不会被改变。⽂文 中具体测试了⼤大数据流传输的情况。作者利⽤用洋葱路由客户端去获取4MB的⽂文件数据，在有 优先级的⽹网络和没有优先级的⽹网络中各测试了200次。结果如图6. 从图中来看，两条曲线相互交错，不能看出明显的优劣。作者利⽤用分布函数的KS统计 情况，推导出从数理统计⾓角度来看两种情况没有区别。⽽而且，作者认为⼀一般情况下⼤大⽂文件的 传输⽤用时较多，例如电影下载往往都要⼏几⼗〸十分钟，如果时延有增加，⽤用户较为容易介绍。 5.总结 总体来说，⽂文章针对早期洋葱路由存在的数据包调度在性能上的问题，提出了⼀一种基 于EWMA的设置优先级的调度办法，使得交互类的数据能够被更快发送，⽽而⾮非交互类数据没 有收到明显的影响。 5.1⽂文章的优点 在笔者看来，这篇⽂文章的优点⼀一共有三个。 ⾸首先，作者⽤用⼀一个simple idea解决了洋葱路由⽹网络中较为棘⼿手的⼀一个问题。整个⽂文章思 路较简单，源于作者解决问题的思路清晰，⼊入⼿手点容易。这个和作者平时⼤大量的实验测量和 反思是分不开的。 然后，作者利⽤用了⼀一个有效的办法使得性能有显著的提升。即使清楚洋葱路由中这⼀一问 题，想到这样的办法也不是⼀一蹴⽽而就的。⼀一⽅方⾯面作者知道⽆无法直接通过数据包的内容来区分 两类数据，两⼀一⽅方⾯面作者考察清楚了两类数据的性质，即交互性的数据往往通信量较⼩小，是 猝发的，⾮非交互性的数据往往通信量⽐比较⼤大，是持久的。通过这两点思考，作者才可以提出 记录数据量这⼀一简单有效的办法来处理这个问题。 最后，作者通过全⾯面细致的实验验证了⾃自⼰己的整个理论体系。作者先在实验环境下进⾏行 探究测量，然后在实际⽹网络中验证测量。即考察了对交互类数据的提升情况，有证明了对⾮非 交互数据影响不⼤大。除此之外，作者还探究了不同节点的情况，不同时刻的情况。所以作者 的实验是有⾜足够说服⼒力的。 5.2关于⽂文章改进的两点思考 在读⽂文章的时候，笔者对于⽂文章有两点疑问，觉得有两⽅方⾯面待改进的部分。 ⾸首先，⽂文章中提出的算法是通过对OR修改⽽而实现提升性能的，但是这样做有暴露传输 路径的可能。当攻击者对⽹网络中很多节点（洋葱⽹网络现有节点并没有上万）进⾏行实际测量之 后，攻击者有可能根据传输过程中的特性来推测传输路径是什么，即推测整个数据包通过了 哪些节点。 /6 7
    然后，⽂文章关于优先级的调度存在不全⾯面的地⽅方。当攻击者利⽤用优先级的特性来对某个 节点进⾏行攻击，例如持续传输具有猝发性的数据，那么通过这个节点的其他数据可能会因为 优先级问题⽽而使得传输不能进⾏行或者传输速率变得极低。对于后⼀一个问题，笔者认为只要对 优先级进⾏行适当的调整，对⼤大的数据流的优先级设置保护，让他们的优先级不⾄至于⼀一直处于 队列中最低优先级即可。当⼀一个数据流的优先级长期处于最低情况时，可以适当调⾼高其优先 级（例如采⽤用轮询的办法），使得数据传输路径不被打断。 /7 7
    分享到：
    赞 收藏

    相关推荐

    资料库

    网络技术

    共收录2367份资料，累计7个分类，关注成员有19位，主要包括：综合布线,网管软件,网络监控,网络设备,其它,系统集成,网络基础

    热门标签

    综合布线 网管软件 网络监控 网络设备 其它 系统集成 网络基础

    最新资料