会议论文概况

今年的SIGCOMM会议从225篇中论文中录用了39篇，录取率为17.3%。会议一共5天时间，从周一持续到周五，中间三天是论文主进程，周一和周五是各类workshop和教学。为期三天的主进程以获得SIGCOMM终身成就奖的Jim Kurose教授的演讲开场。据说全世界的网络学子们都读过他的书，正是写《计算机网络–自顶向下方法》的这位教授，阐述了他对计算机网络的教育、科研、教学和服务的一些观点。

登录主会现场的总共有41篇论文，包括39篇同行评议论文和2篇CCR最佳论文。其中39篇论文划分为11个技术session，分散在周二到周四的6个半天中举行。2篇CCR论文放在周四下午的收尾部分。21个poster、18个demo、13篇主会论文的poster/demo和6篇工业界的demo交错安排在茶歇时间，这让会议的总体节奏显得很紧凑。

当前Openflow协议中的消息基本可以满足我们对SDN交换机的管理需要，但是在很多情况下，我们更希望能够与openflow交换机交互自定义的管理消息，这就需要用到openflow的实验消息(experimenter messages)。本文以SDN软件交换机ofsoftswitch13为例，来说明如何实现通过自定义的experimenter消息来与交换机通信。

总体介绍

ofsoftswitch13是支持Openflow1.3的开源SDN软件交换机，由爱立信公司的CPqD团队开发。工程以Stanford大学开发的openflow1.0软件交换机为基础，主要新增了对Openflow1.3协议的支持。

ofsoftswitch13是一款由C语言实现的轻量级的SDN软件交换机，代码总量在5-10万行之间。在功能上比较完整的对Openflow1.3协议进行了实现， 最重要的两个部分是udatapath和secchan。其中udatapath是交换机中数据包的处理通道，secchan负责交换机与控制器的连接。

本文主要对udatapath部分的内容进行解析，具体来说将从三个方面展开：一是交换机udatapath中的核心结构，二是交换机对来自控制平面消息的接收和处理流量；三是交换机对来自数据平面的数据包的处理流程。

问题描述

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

出自leetcode第169题，最直接的解法如下:

排序取中

问题描述

集合覆盖问题的一个实例$ \langle X,F \rangle $ 由一个有限集$X$及$X$的一个子集族$F$组成。子集族$F$覆盖了有限集$X$。集合覆盖问题就是要找出$F$中覆盖$X$的最小子集$C^*$，使得$|C^*| = min \lbrace \; |C| \;|\; C \in F \bigwedge C覆盖X \rbrace $ 。

证明集合覆盖问题是NP难的。

证明NP难问题的一般步骤

要证明集合覆盖问题是NP难的，我们只需要证明集合覆盖问题的判定问题是NP完全问题即可。而要证明一个判定问题属于NPC问题，一般需要两个步骤

主要内容

由于SDN软件交换机ofsoftswitch13的wiki不够完善，支持的平台有限，想要使用该交换机的新手即使按照其文档一步一步做，也经常会遇到一些问题。目前，我发现部分常见的问题google上还找不到答案，在这里总结一下。

写在前面

ONetSwitch是我们实验室自主设计研发的，基于Xilinx Zynq器件的SDN交换机。ONetSwitch具有从硬件逻辑到软件控制全可编程的特点，因此这是一个非常理想的SDN科研平台。目前也确实有不少科研团队在使用，主要包括我们实验室。

正是由于ONetSwitch在软硬件方面都提供了非常灵活的可编程性，ONetSwitch交换机整套系统的使用就变得非常复杂：硬件层面的可编程性要求你得非常熟悉Xilinx Vivado环境下的FPGA开发，软件层面的定制需要你熟悉Xilinx Zynq AP Soc平台的设计。

虽然在Github wiki上有比较详细的介绍，但是对于刚刚接触ONetSwitch，又想快速进行科研实验的新手(主要是学生们)来说，这个过程还是有一定的困难。我接触ONetSwitch一年多了，主要做的是软件层面的工作，踩了很多坑，也积累了一些经验。因此我在这里写出来，分享给OnetSwitch的用户们，也给实验室的学弟们一些快速入门的资料。

复赛问题

给定一个带权重的有向图G=(V,E)，V为顶点集，E为有向边集，每一条有向边均有一个权重。对于给定的顶点s、t，以及V的子集V’和V’’，寻找从s到t的两条不成环的有向路径P’和P’’，使得P’经过V’中所有的顶点，而P’’经过V’’中所有的顶点（对P’经过V’中顶点的顺序以及P’’经过V’’中顶点的顺序不做要求）。

若不同时存在这样的两条有向路径，则输出无解，程序运行时间越短，则视为结果越优； 若同时存在这样的两条有向路径，则输出得到的两条路径，按下列优先级从高到低评价结果优劣：
1、 路径P’和P’’重合的有向边个数越少，则视为结果越优；
2、 在两条路径重合的有向边个数一样的情况下，两条路径权重总和越少，则视为结果越优；
3、 在上述两个指标一样的情况下，程序运行时间越短，则视为结果越优。

问题定义

给定一个带权重的有向图G=(V,E)，V为顶点集，E为有向边集，每一条有向边均有一个权重。对于给定的顶点s、t，以及V的子集V’，寻找从s到t的不成环有向路径P，使得P经过V’中所有的顶点(对经过V’中节点的顺序不做要求)。

若不存在这样的有向路径P，则输出无解，程序运行时间越短，则视为结果越优；若存在这样的有向路径P，则输出所得到的路径，路径的权重越小，则视为结果越优，在输出路径权重一样的前提下，程序运行时间越短，则视为结果越优。

目录

1. 主要内容

2015年，Google在SIGCOMM会议上发表论文《Jupiter Rising: A Decade of Clos Topologies and Centralized Control in Google’s Datacenter Network》，比较详细的阐述了Google在过去十多年中数据中心网络的创新和演进。

本文主要基于该论文对Google数据中心网络技术的发展进行分析和总结，同时给出个人理解和看法。Google的论文的主要思想如下：论文提出了Google为了克服高昂的成本、操作的复杂性、有限的规模可扩展性问题，而实施的解决方案；阐述了Google十年间逐渐发展的五代数据中心网络。主要包含三个方面的主题。

第一，利用多级互连的Clos拓扑网络技术，使得Google可以通过商业交换芯片来搭建大规模的交换网络系统。第二，传统网络中大量通用的，分布式的，非常复杂的网络路由和管理协议虽然可以支持任意的部署方式，但是这对于需要单一操作平面的数据中心网络却矫枉过正了。Google建立了中心化控制的，支持全局配置的数据中心网络。第三，模块化的硬件设计加上简单的、高可靠性的软件使得Google可以设计出同时支持数据中心内部集群间路由和外部广域网路由的系统。

Google的第五代数据中心网络Jupiter已经在全球几十个站点运行部署，网络带宽已经达到1Pbps，这比十年前提高了十多倍。Jupiter足够10万台服务器每台之间以10Gb/s交换信息，可以在十分之一秒之内读取所有美国国会图书馆的扫描数据。