Author Archives: Mike

什么是 4G LTE 中的 Attach,Paging 和 Detach

(This blog uses google drive to store image files.)

Rephrase from LTEInspector: A Systematic Approach for Adversarial Testing of 4G LTE, Section II-B, by Hussain, Syed Rafiul, et al. at NDSS ’18.

↓ 这里有一个示意图,请确认能够正确加载

名词解释:

  • UE:user equipment, 终端设备,即手机
    • 手机有一个唯一识别码:IMEI, international mobile equipment identity
    • 手机有一张 SIM 卡,SIM 卡有一个唯一识别码:IMSI,  international mobile subscriber identity, 并且 SIM 卡自带一个 cryptographic keys 来让 EPC 验证 SIM 卡。
  • eNodeB:evolved node B, 即 4G 使用的基站(base station)的简称。
  • EPC:evolved packet core, 即 4G 使用的核心网的简称,一端连接 eNodeB,一端连接 Internet
    • MME:mobility management entity, 在 EPC 端管理维持 UE 的 attach,detach 等过程
    • HSS:home subscriber server, 保存 UE 的识别信息,即 IMEI,IMSI,生成零时会话 keys

Attach

  1. UE 和 eNodeB 建立连接
    • 时机:UE 重启
    • 动作:UE 广播 system_info_block 给所有的 eNodeBs
    • 结果:UE 选择信号最强的 eNodeB 建立连接
  2. UE 通过 eNodeB 向 MME 发送 attach 请求
    • 消息:UE 向 MME 发送 attach_request
    • 内容:明文 IMSI/MIEI, 及 UE 支持的安全机制
  3. MME 向 HSS 验证 UE
    • 内容:MME 向 HSS 发送 UE 的 IMSI
    • 反馈:HSS 验证通过,向 MME 返回本次会话使用的 authenication_challgenge
  4. MME 向 UE 要求处理 authenication_challgenge
    • 消息:MME 向 UE 发送 authentication_request,携带 authenication_challgenge
    • 目的:要求 UE 使用 SIM 卡中的 key 加密这个 authenication_challgenge
  5. UE 向 MME 返回 authentication_request
    • 内容:UE 使用自身的 key 加密 authenication_challgenge
    • 目的:通过 UE 的加密结果,MME 能够判断 UE 的真伪
  6. MME 选择安全机制/加密方式,发送至 UE
    • 消息:security_mode_command
    • 操作:如果 5 中,UE 返回的内容通过验证,MME 在 2 中 UE 提供的安全机制中选择一种作为接下来通信的加密方式。
  7. UE 确认加密方式,发送至 MME
    • 消息:security_mode_complete
    • 此外:这个过程也确定了接下来加密使用的 会话 shared keys
  8. MME 向 UE 发送 attach_accept
    • 特点:已经用 shared keys 加密
    • 内容:GUTI,globally unique temporary identity,本次会话使用的手机唯一识别码,之后可以不用再使用 IMSI/IMEI
  9. UE 向 MME 回复 attach_complete

Paging

UE 没有数据发送的时候会进入休眠模式,并被周期性的唤醒,这个过程被称为 Paging。

MME 发送 Paging

  1. MME 希望向 UE 发送 call 或者 SMS 的消息
  2. 所有在 tracking  area 的 eNodeBs 广播给所有 UEs 这个 paging 消息
    • 这个paging 应该携带 GUTI
    • 如果出现异常情况,paging 消息将携带 IMSI,对应 UE 收到之后应该进入 detach, 然后 re-attach

eNodeB 发送 Paging

  1. 在系统发生变化或者紧急情况的时候,例如,地震,安珀警报(Amber)。

Detach

  1. UE/MME 发送 detach_requet
  2. 接收端回复 detach_accept

How to Read a Paper 阅读笔记

ACM Sigcomm CCR 07′

阅读一篇论文可以有三遍:

第一遍:

  • 时间:10 分钟
  • 操作:阅读标题、摘要、Introduction、Conclusion、每章标题和小标题,过一遍 References
  • 收获:文章分类、Contributions、写作水平

第二遍:

  • 时间:1 小时
  • 操作
    1. 阅读正文,跳过证明
    2. 在文章的边角写下 key points
    3. 标记未来需要阅读的 references
  • 收获:没有理解也没有关系,如果不想理解它,就可以丢掉了。

第三遍:

  • 时间: 1 小时 到 5 小时
  • 目标: 尝试 虚拟 re-implement 这篇文章
  • 操作
    1. 识别和思考文章的每一个 assumption, 思考自己会如何处理它们
    2. 写下 future work
    3. 写下文章的 strong and weak points

Survey

  1. Google 搜索近年的 3 – 5 篇文章,读第一遍
  2. 读他们的 related work,看是否引用了 survey, 读 survey, done
  3. 否则,访问他们共同引用的作者,分析他们最近发表的会议
  4. 研究会议近年来的内容,并分析会议paper 的引用,找到并阅读最重要的那些

Open Networking Summit 2018 参会笔记 Day 2

(This blog uses google drive to store image files.)

  • 时间:2018年3月27日
  • 地点:InterContinental Los Angeless Downtown, Los Angeles, CA, USA

会议第二日概况

Open Networking Summit 的第二天上午的活动包括昨天还没有结束的 Development Forums 的尾巴,和参会厂商的演示。下午首先是会议的开幕活动和全体 Keynotes。最后是 2 个 45 分钟的小会议室报告会。每个时段都有平行八个报告会同步进行。

在平行报告会中,我选择了参加 Ciena 主持的 Open Network API Development 和 中国移动、VMware 联合主持的 Multi-Could Practices with NFV and ONAP。并在会后和中国移动研究院做报告的 Senior Project Manager 有了简短的交流。

厂商展示

和学术性的会议不同,Open Networking Summit 更像是产品展销会合作洽谈会。让我一个来寻找学术课题的 Ph.D. Student 一开始有点无所适从,不知道该如何入手。但是慢慢融入了之后也会发现其实业界也是广阔天地,大有作为。

(我起的晚了点),到的时候,和第一天的冷清不同,大部分厂商的展台都已经布置好了,热闹非凡。并且有热情的小姐姐招揽参会者,发放纪念品。我也领到了一大堆厂商的纪念品和开源项目的贴纸。


ONAP,Kubernetes 和 DPDK:要我选择这次 Open Networking Summit 的关键词,我会毫无疑问的选择 ONAP,Kubernetes 和 DPDK。无论是厂商的站台展示,还是所有的报告会,这三个关键词能够囊括超过 80% 的内容。

下面我把一些我感兴趣的研究相关的项目罗列一下。

  • Yunshan (云杉) 网络的展台是中国特色最浓厚的展台。他们的展板上展示了很多他们为中国的 500 强企业提供的解决方案,包括 监控云,私有云和金融云。云杉的 CEO 表示,他认为目前中国企业网络的 SDN 化还不够彻底。国内企业网络的 SDN 项目依然有很大的发展空间。同时,他们也致力于 Intend-Based Network 的研究。他认为这是未来网络的一个发展方向。

    云杉公司提供的旅游纪念品是一对小碟子。
  • DMM:是一个用户态网络加速的项目。这个项目的思想来自于著名的 NSDI 14’ 的文章 mTCP,在用户态重写 TCP 栈的项目。在这个项目中,他们重写了 socket 相关的代码,并且为用户提供了两种模式(Dual Mode),用户可以自主的选择流量通过 kernel space 转发还是 user space 转发,实现网络的加速。
  • SRIOV-DPDK Networking with Kubernetes: 这个项目的核心是用 DPDK 来实现家属 Kubernetes。在这次 Summit 上,用 DPDK 来加速各类项目的开源项目的展示有很多。可以看出 DPDK 虽然推出有一段时间了,依然很火。
  • ARM:这个项目展示了 ARM 对 Kubernetes OPNFV Edge Computing 的支持。当我问 ARM 的工作人员为什么 ARM 对这些开源社区和开源项目如此的支持的时候。ARM 的工作人员微微一笑,说,如果大家都用这些开源项目,那么大家就都会来买我们 ARM 的芯片呀。
  • NOKIA:诺基亚的工作人员热情的拉着我要我给他们的 4G 可移动便携式家用基站拍个照。
  • ONAP:  虽然 ONAP 是这次 Summit 的最火热的关键词,我一开始并不了解 ONAP 的细节。
  • 阿里云:和会场热闹气氛形成反差的是阿里云的展台。阿里的展台没有布置任何的显示器或者演示,让参会者没有驻足的理由。这也导致了阿里的展台前门可罗雀。笔者尝试去搭讪也没有获得什么信息,只是得到了一个介绍阿里云产品的小册子。阿里云应该是国内最早开始商业公有云服务售卖的厂商之一,已经有了及其成熟的技术和商业模式。因此对 Open Source Networking 兴趣不大也可以理解。

Open Networking Summit 2018 参会笔记 Day 1

(This blog uses google drive to store image files)

  • 时间:2018年3月26日
  • 地点:InterContinental Los Angeless Downtown, Los Angeles, CA, USA

前言

Open Networking Summit (North America) 是 Linux Foundation 举办的一年一度的开放网络峰会,横跨工业与学术界,聚焦 SDN, NFV,未来网络体系结构等议题。多年耕耘,在领域内已经有了很大的号召力,今年吸引了 30 多家相关企业的赞助和参会。

笔者知道 Open Networking Summit 源于 SOSR (Symposium on SDN Research)。SOSR 是 SDN 领域内最富影响力的会议,作为 Open Networking Summit 的一个 Co-located Event 举办。笔者最近两年投稿,都被审稿人花式打脸,惨遭拒稿

今年收到拒信后,导师说,SDN 研究还是应该看清工业界的发展方向,要做能够落地,有实际应用前景的研究;Open Networking Summit 有很多工业界的 talk,时间也刚好是你的春假,不妨自费去看看吧。

出发 

会议一共有四天,从周一到周四。但是,其实正式的 Keynote 从周二下午才开始,周一和周二上午是各式各样的 Open Networking 框架的 Developer Forums。本着节约一天住宿费的崇高目的,笔者选择了周一早上八点四十从埃文斯顿飞往洛杉矶。加上时差的因素,刚好可以赶到洛杉矶周一中午的午饭。

春假的第一天(虽然PhD并没有春假),在闹铃声中醒来,笔者第一次看到了埃文斯顿凌晨六点钟的太阳。

匆忙下楼,打开 Uber,准备打车去机场,却被迎面扑来的价格吓呆了。“60刀,它怎么不去抢!“。还好笔者见得多的,西方的哪个打车软件没有用过,连忙打开了 另外一个打车软件 lyft。lyft 去机场的价格就正常多了,只需要 35 刀。笔者赶紧点下了叫车键,生怕 lyft 反悔了。坐在车上,回想着笔者刚刚用自己的聪明才智赚了 25 刀,不由的为市场经济这只看不见的手鼓掌。

由于起的太早,上飞机就睡着了。等到醒来时,已经能够看到被云雾缭绕、终年积雪的落基山脉了,甚是壮美。等笔者省吃俭用买了车,第一件事情就是开去黄石公园爬山。从飞机上看下去,不论落基山脉以东还是以西,都是广袤的平原和耕地,再想想我国只有 8% 的可耕地面积,不由得感叹米国自然资源的优渥。

飞机过了落基山脉,不久就开始降落了。因为除了笔记本和几件换洗的衣服,没有携带任何行李,下了飞机,便直奔会场。

在路上,透过汽车的窗户,看到的便是电视中的加州美景。明媚的阳光下是碧海蓝天,映衬着近处的椰子树,显得格外可爱。汽车的 Radio 里正放着的传世名曲《加州旅馆》,心里也不由得也跟着哼了起来,”Some dance to remember ~, Some dance to forget ~ “。

Open Networking Summit 初识

今年的会场选在洛杉矶 Downtown 一个刚新建的五星级酒店。一进入酒店的会议楼,就能看到今年会议赞助企业的巨幅展板,几乎囊括了SDN 业界的主要玩家。

但是由于正会明天下午才开始,所以会场还在繁忙的布置阶段,参会厂商的演示大部分都还没有准备好。

会议第一天概况

会议的第一天除去光纤、EE 相关的内容,有四个和我们相关的 Developer Forums 在并行进行,包括:ONAP、OpenDaylight、OPNFV 的 Developer Forums 和 Open Networking Foundation (ONF) Vision Day 的讲座。

笔者在这四个 Forum 中各选了一个 Section 参加。

1. ONAP Use Case and Functional Requirements

1:00 PM – 2:30 PM

这个讲座由很多 Speaker 各讲 5 分钟组成,分享他们使用 ONAP 的 Use Case,并回答提问。但是这个讲座并没有精心准备和排练,很多 Speaker 用毫无激情的语速语调快速的读完了 Slides 中的备注就匆忙的结束自己的 5 分钟。内容很多都是”这一块我们还在做,我们还没有做完,大家有什么问题就问吧。“这个情况和笔者之前调研 ONAP 相关现状的情况比较吻合,这似乎是一个完成度还不是很高的项目。

听完了这个 Section,我依然不能准确的回答 ONAP 到底想做什么,ONAP 目前已经完成了多少东西可以开放给用户使用?看来笔者接下来还需要多做一些工作。(在接下来的几天,我和 ONAP 和的 开发团队成员,已经运营商 ONAP 相关的开发小组成员有了面对面的交流,终于才搞清楚了 ONAP 的目的和现状,这个可以之后再谈。)

在这个部分中,印象深刻的是一个来自 AT&T 的 Speaker, 分享了他们使用 ONAP 来设计 Open Source Access Manager 的一个 Case。虽然五分钟的时间并没有能够让他分享多少内容,但是,他提到了他们已经完成了该项目的 Wiki,大家感兴趣可以之后去阅读。

另外一个来自 AT&T 的开发小组分享了他们在 5G 中使用 ONAP 的一个 Use Case。 一个毫无激情的印度演讲者。用极快的语速把 slides 的备注读完了。通过下面的截图可以看到,他们想使用 ONAP 来同时管理 5G 的 Design 和 Runtime。

此外,听到的最多的关键词就是 ”Beijing“,虽然 Speaker 来自五湖四海,世界各地,有各式口音。但是,似乎很多 ONAP 相关的开发小组都坐落在北京。这一定有深层次的原因。

2.  OpenDaylight Project Breakout: Kernel Project Planning, What Utilities are Available to You From Project Infrautils.

1:00 pm – 3:00 pm

和上一个 ONAP 还在画饼的讲座相比,OpenDaylight 的 Developer Forum 就是纯正的技术研讨会了。我认为,这是因为 OpenDaylight 已经时很成熟的 SDN 控制器了,(或者他们更愿意称为网络操作系统)。

讲座首先讨论了他们关于 Kernel 模块接下来的开发计划(我去的时候已经基本讲完了)。接着另外一个开发者讲了他们准备在 OpenDaylight 加入的新模块 Infrautils。这个模块是为别的项目提供工具的项目。其特点是完全的独立与别的项目,例如,mdsal,YANG,只依赖于 odlparent。如下图所示。然后开发者就激情演绎的讲了 1 个小时这个模块的设计细节。

我下了飞机之后滴水未进,直奔会场,到这时已经饿的不行了,在酒店旁边找到了一家的拉面店。

3.  Open Networking Foundation Vision Day: Operator Deployment Plans

4:15 pm – 5:45 pm

要我来选择今天我参加的最有价值的活动,我肯定会投票给 ONF Vision Day。我也很后悔错过了他们前面的活动。

当我抵达 ONF Vision Day 活动的会议室的时候,刚好是 Operator Deployment Plans 的开始,ONF 的主持人说:”如果你们刚到,错过了我们之前的活动,不要担心,我帮大家总结提炼一下。我们刚刚宣布:

属于学术界的开源网络时代已经结束,现在工业界才是 Open Networking 的主导!“

接着 ,8 家工业界的企业,包括:Comcast, AT&T, Turk Telekom, T-MObile, Telefonica, China Unicom, NTT, Google 分别展示了自家对 Open Networking 的使用情况。

  • 来自 AT&T 的演讲者说,他认为,ONF 致力于推进 ”Real“ SDN 和 microservices。但是我们应该思考的问题是,我们真正需要的是什么:”what we are looking for?“。他认为,”What you built is not as important as how you built it“。
  • 来自 Turk Telekom 的演讲者首先介绍了自己一番,说他们是土耳其最大的电信运营商,有超过 41.7M的用户,然后表了一番忠心,表示他们会大力支持 ONAP 的发展,并简短的展示了一个他们使用 ONAP 的来使用 Subscriber Aware Dynamic SFC 和 vOLTHA 的 use case。
  • 来自 Telefonica 的演讲者表达了他们对 CORD 的特别是 vOLTHA 的浓厚兴趣。
  • 来自 中国联通 (China Unicom)的演讲者分享了很多内容,他提出了一个 ”Telecom Cloud“的概念,脱胎于 ”Edge Cloud“。同时我也第一次听说了”Network Edge as a Service“ 这个概念。接着他说,他认为 CORD 架构是一个 ”potential“ open-source platform for edge-cloud,因此,中国联通对 CORD 也有很大的兴趣。同时他直言不讳的说,他认为 white-box 比现在已有的 交换机产品要贵,这是不应该的。因为用户(中国联通)从 white-box 厂商获得的支持是极其有限的,和传统交换机相比没有任何优势。而且白盒交换机没法替换传统交换机的问题在中国特别严重。他说,由于政策的支持,中国早已实现了”光纤入户(Fiber to the home)“,本身网络的价格已经极其低了,并且带宽满足很长一段时间的发展。因此,我们并没有真正的需求来进行网络的 Open Source 升级。
  • 来自 NTT Communications 的演讲者说,他们早在 7 年前,就将 OpenFlow 部署到了他们的 Cloud。接着他讲述了他们现在 ”Transport SDN“的工作,如下图所示。
  • 最后,来自 Google 的演讲者讲述了他们宏大的计划:”Move from OpenFlow to P4Runtime“。在此之前,我并不认为 P4 会在短期内被工业界部署。被 Google 这个计划大吃一惊。接着他展示了Google 关于 P4 的完整计划和目标:”P4Runtime for new applications“, “Build controller & Switch Support”, “Refine P4 programs, make work at large scale”,最终完整的将 SDN 系统迁移到 P4 上面去。他认为:”The future of networking is open source”.

最后 ONF 主持人的话也然我产生了很大的共鸣,他说:

回首五年前,我们完全不敢想象,在运营商的网络中会使用 write box 交换机,使用 Open Source 软件,但是现在已经成为现实。而且还会进一步扩大影响力,会有更多的企业加入进来。这样的现状让人 ‘So exciting!‘

一颗赛艇。

插曲:报告会结束了之后,笔者很想和来自中国联通的大佬聊一聊他们对 CORD 的开发和部署情况。但是有点害羞,正在犹豫具体聊些什么的时候。没想到中国联通的大佬一个健步就把 ONF 的大佬拦了下来,开始和ONF 的大佬用英语尬聊。看到这里,笔者不由得感叹,大佬之所以能够成为大佬是有原因的。有了这个榜样,接下来三天的会议中,我都会有意识的锻炼自己,有任何想法的时候都果断的和别人搭讪,这么好的面对面交流的机会不能浪费。也因此收获了很多。

下班收工

DPMS阅读笔记 – Optimal Deployment of Distributed Passive Measurement Monitors

From: ICC 2006 CCF C
Key Words: DPMS Huc Counter Distributed_Passive_Measurement
Author: 2 Biu Liu 4 Shifang Gao 5 Dapeng Wu from U of Florida

KYH的一句话总结:
在全网上放置monitor做流量测量,monitor放置的越多测量的越准,但是花费也会越大,所以是一个权衡。分析这个问题太复杂了,所以作者提出了一个 CCP 问题,假定用户有一个心理的monitor覆盖率阈值,求放置的方案达到这个阈值满足一个置信度即可。同时提出了 BCP 问题,假定用户有一个预算上限,在给定预算的情况下怎么放置满足覆盖率阈值和置信度,覆盖率取到最优解。显然都是NP-hard问题,直接用遗传算法求解。皆大欢喜。

0. Abstract:
通用的 centralized per-flow measurement 会导致内存带宽和大小问题。Paper 提出了 DPMS (Distributed Passive Measurement System,只需要在一些位置放置 monitors 来采样随机流量(stochastic),优化目标是覆盖率最大。

文章将问题建模为 SCCO (Stochastic Chance Constrained Optimization), 提出了 HI (Hybrid Intelligent)方法,包括 uncertain function approximation 和 genetic algorithm. tradeoff 是 覆盖率和 cost (small number of monitors).

1. Introduction:
Flow-level 被动测量分为 centralized / distributed.[1-3]指出 centralized 会有内存和带宽的问题。所以 paper 讨论 distributed. DPMS 通过降低采样速率来降低 内存带宽需求。但是提高速率 和 更多的 monitors 可以提高覆盖率。所以是一个 tradeoff.

IPMON[4] 是在 Sprint IP 放置了 distributed,但是没有考虑 tradeoff. [5]讨论了 tradeoff,但是没有考虑流的random. Paper 讨论了 tradeoff 和 random.

2. Formulation:

2.1.Setting
flow 定义为 Same Source Destination IP. Node-based monitor 能够在 node 内部实现,能够 monitor 所有 connceted 的 link. 假设 flow 是 single path, 所以我们能在任何一个path上观测流。. (KYH: 这个假设也太强了,把建模简单太多。) 采样速率在每个monitor上独立配置,不同的流在一个monitor上是相同的被采样速率。

(1)式给出了放置一个 monitor ci 的 cost. 为
C + a (采样速率 / 最大速率)^m.
其中 C 是恒定花费。 a, m 是常量 (KYH:真是一个简单的定义,另外,凭什么说速率的cost可以直接除出来)。

(2)给出了总花费: Sum(ci * xi). 其中 xi = 1 表示 monitor 放在 node i 上.

假设 1) 流是fluid,也就是单包size为无穷小(KYH:也就是可导,(●’◡’●)).2)随机变量 fj(t) 表示流 j 在 t 的traffic. 3) fj(t) 是 stationary 和 ergodic process 的.(KYH: ergodic process: 平稳随机过程中任一随机样本函数的时间平均值与无限多个随机样本函数在同一时刻的平均值相等,即时间平均等于集合平均。)有了3)的假设,fj(t)就变成了 fj. (KYH:这不就是作弊么。。。)

流能被测量当 Rate i 大于 flow j.

(3)式给出了采样率 rij = (qi xi yij) / fj . 其中 qi 是 node i 的采样率。xi 同上, yij = 1 表示流 j 通过 node i. 所以就是 Rate i / flow j

(4)式给出了采样到流 j 的概率, Rj = 1 – Sum i (1 – rij) (KYH: 就是 1 减所有节点都采样不到 j 的概率)

(5)式定义了采样覆盖率 M = Sum j (Rj) / n ,其中 n = number of flow.

2.2. SCCO Model
(KY:SCCO 这个名字可以看出,年轻的 Huc 这个时候还没有形成自己的起名风格)

因为 f> 向量是 stochastic, 所以 M 也是 stochastic. 因此引入 SCCO,通过 probabilistic bound 和置信度 b 来讨论问题。 (KY: f> 向量就是每一条流的Rate组成的一个一维向量,使用线性代数来讨论问题可以提高文章的姿势水平。)

用户最关心的是 coverage. 所以设计了CCP (Coverage Constraint Problem)问题. 优化目标是 Min 式(2) 满足
式(6) Pr{M >= T} >= b, 其中 T 是预定义的覆盖率阈值.

对ISP来说,最关心的是 Budget,应该添加一个 Budget 的限制.文中称 BCP (Budget Constraint Problem)问题。描述为
式(7) Mo = sup { r | Pr{M >= r} >= b}

(KY: 这个式子写的太难懂了。 首先 Mo 之前没有定义, o 应该指的是 optimistc, 所以这里求最优的 M 全网平均覆盖率。 sup 这里应该是上界 Supermum 意思。我先理解为了 支持集 和 支持度,都想不通。这个上界的表示真是不好。

所以是求集合 r 的上界。 当 r 持续上升的时候, Pr(M >= r) 的概率必然持续下降, 所以这个概率满足置信度 b 的 r 最大值就是所求 )

这些都在假设有 ISP 有确定的 budget B, 也是就满足
式(8) sum(ci xi) <= B.

总结:这章给出的核心假设有:

1) 流是 single path
2) 流无限可分
3) cost 满足 qi / L 的经验公式
4) fj(t) 可以看作 fj
5) 存在覆盖率阈值 T, ISP 预算 B

两个优化目标: CCP BCP

3. HI 算法

2中的算法和传统的随机过程优化为题都不同。但是如果 uncertain functions 是 determined, 那就和经典的优化问题一样了。所以核心是 determined 化这个问题。Paper提出 HI算法, 1) uncertain approximaiton 2) optimization. 3.1 Uncertain approximation (KY:引入上文提到的 f> 向量,下标为 k,也就是有 k 个 f> 向量)

式(9)给出 indicatior I(f>) = 1 if M(f>) >= T else 0
式(10)给出期望 E[I(f>)] = Pr{M(f>) >= T }

用 N’ 去 count 满足 M(f>) >= T 的情况,也就是
式(11) N' = Sum{ I(f>) }

这个就是经典的 SLLN (Strong Low of large number) 问题。
(KY:原文这里写错了,应该是 Strong Law, 强大数定义,即在无限次试验下,均值等于期望).

所以就有
式(12) N’ / N = E[ I( f> ) ] ,即均值 = 期望

带入就是
式(13) Pr{ M( f> ) >= T } = N’ / N

(KY: 至此,原文解出了 式(7) 中的优化目标,就是 count 一下 N’,虽然我有点不服。 )

然后给出了流程1:

random generate f_k > by flow rate distribution function // 这个function从哪来
N' = 0
for k=1 to N
__if M( f_k> ) >= T
____N'++
return N' / N // 这个值就是近似的覆盖率

CCP问题就算解了,对于BCP, 要求 Pr{M >= Mo } >= b, 显然等价于 Pr{M >= Mo} = b.

式(14)给了一个 indicator I(f>) = 1 if M >= Mo else 0
同样给一个 counter N’ 来记录 M(f_k>) >= Mo, k = 1 to N

同样用 SLLN 的方法,得到
式(15) N' / N = E[ I(f>) ] = Pr{ M >= Mo } = b

-> N' = ceil(bN),给出了流程2

random generate f_k > by distribution function // 这又是什么function
N' = ceil( bN )
for k = 1 to N
__get M_k by f_k>
sort(M_k)
return M_N'

3.2. Optimization Method

[6]中证明了 budget maximum coverage problem 是 NP-hard, 所以用 heurisitc 求解。

GA (Genetic Algorithm) 遗传算法大法好[7,8], 因为
1) 对于大范围的目标函数,找到全局最优解效率高
2) Tabu, Simulated Annealing 模拟退火 同样有 1) 的特点,但是DPMS用它们写代码太难了
3) GA 的收敛性已经被证明了[9,10].

流程为:
1) 随机产生染色体 chromosomes 作为 solution candidates
2) evaluation and selection
3) 产生新的 chromosomes by 2) 的交叉 和 变异 crossover & mutation
4) 判断收敛 或者 predefined iteration times

染色体定义为 V = ( x1…xl, q1…ql ), x1 = 1 代表 1号node有monitor,q是采样率。 然后产生他们的 crossover, 通过 V1 和 V2 交换第 n1 到 n2 位置的基因,产生 V1′ 和 V2’,这样就有遗传算法的族群了. 然后randomly产生 position m1-m2 的值,这样就有变异了.

然后是评估,通过 rank-based, 通过它们产生的 object 来排序,下标代表位次, 然后归一化它们的匹配度fitness通过fitness(Vi) = a (1-a)^(i-1). Paper 特别指出,实现上用了 轮盘算法 roulette-wheel

(KY: 这块建模求解就是怎么粗暴怎么来)

4. Experiments and Evaluation

4.1. Settings

生成了 4 种分布的流量: Bimodal, Uniform, Exponential, Constant (双峰,均匀,指数,常数). Bimodal 是通过混合两个 Exponential 产生的. Constant 的 Rate 是 300Mb/s.

用了 14 node 的网络拓扑[12],(1)式中, C,a,最大速率,m 分别为 1,0.5,500,2. 置信度为 0.9.

4.2. Result

图4表示覆盖率和Cost之间的关系,对应CCP问题. 其中 curvers of deployment cost are approximately the convex functions of coverage, which means differential coefficient of cost is larger when coverage constraint is increased.

图5表示覆盖率和 Budget 之间的关系,对应BCP问题。观察到斜率在持续减小,说明后面加钱对覆盖率的增加作用变小了。

图6和图7是图5和图6在 calculation(HI) 和 simulation 之间的差异情况.Paper说,因为 uncertain 的存在,讨论最优解不可行,只能通过 simulation 来检验 HI,图上表明没有差异. (KY: 但是这里的 simulation 是什么,没有说清楚。)

About 10 minutes 在 P4 1.7GHz 上计算出 CCP 和 BCP 的结果. Paper 说 inherent parallelism 可以大幅降低 HI 的时间,然后用文字分析了一番。(KY:我对在 Result 里面分析一番这种做法有一点意见。)

网络拓扑会变,但是mid-nodes一般不会变,或者被 ISP 人为的变,而不是 Random,所以不用考虑。Routing Path会变,但是 not hard to detect,也不是问题. 最后作者给了一个结论,去掉一两个node而不改变部署策略,即使node上有monitor, 其实对覆盖率没有什么影响。全文戛然而止。

(KY:既然都这么说了,我觉得这个问题的 beach mark 应该是,随机的放 n 的 monitor 和作者提出的放 monitor 的方案来比覆盖率,说不定都差不多 (手动斜眼))

为什么 Flow Mod 消息需要使用 out_port 字段

如何灵活操纵 Flow Mod 消息,对掌握 OpenFlow 协议至关重要。在实验中使用最多是通过 flow_add 消息用来添加一条流表。在使用的时候很容易产生疑惑,为何需要填写 out_port 字段。

我第一次产生这样的疑问是在使用 Floodlight 的 J-Loxigen 操作生成流表的时候,当时的代码如下所示

OFFlowMod flowMod = sw.getOFFactory().buildFlowAdd()
.setIdleTimeout(0) //ForwardingBase.FLOWMOD_DEFAULT_IDLE_TIMEOUT)
.setHardTimeout(ForwardingBase.FLOWMOD_DEFAULT_HARD_TIMEOUT)
.setPriority(ForwardingBase.FLOWMOD_DEFAULT_PRIORITY + 1)
.setMatch(match)
.setActions(actionList)
//.setOutPort(outport)
.build();

为了生成一条流表,需要填写的 Time, Priority,Match,Actions 这些参数都很好理解,但是为何独独需要一个 OutPort 参数。如果这个参数指的是 packet 转发的 port 的话,那么和 Actions 里面的setOutPort 字段是什么关系?

Continue reading

A Paly Airplane Game – cocos2dx-html5

Copyright: This game is used for Education. Picture resources used in this game belong to Angry Birds, Rovio Entertainment Ltd. This game is based on a cocos2dx-html5 official demo.
版权声明:这个游戏以教学为目的。其中使用的“愤怒的小鸟”的图片资源文件属于Rovio公司。这个游戏基于cocos2dx-html5官方教程中的一个示例。

Open in a new page

Hello, World!

Hello, world!

This is Mike’s first personal website based on wordpress and Sina App Engine. I cost 28 RMB to buy this domain name for one year. (so cheap~)

This websit shows my Curriculum Vitae, what I am doing now and what I want to learn.

June 11st, 2015