ISSN 
-
随着互联网的普及、用户的增多，业务需求越来越多变，用户对互联网服务类型的跳跃式增加导致互联网流量飞速增长，传统七层架构已经难以满足这种大流量的业务需求，预计2018年的全球互联网流量将达到16×1021字节[1]。因此，欲改善当前互联网面临的问题，应从体系架构上着手，SDN网络架构可有效地缓解传统网络系统中的众多技术难题。
网络资源作为体现网络功能的核心所在，它的浪费就代表网络功能难以最大程度的实现。因此，合理的资源调度已经成为当前互联网必须解决的一个重大问题。通过一系列的策略，资源调度可以使每个资源消费者的需求得到满足，并且使各个资源提供者得到收益。
2006年8月，Google首席执行官埃里克施密特在搜索引擎大会上首次提出“云计算(cloud computing)”的概念[2]。其中资源调度作为云计算的一个核心问题，其主要思想就是将整个互联网的资源汇聚整合起来，通过网络以便利的、按需的方式访问一个可配置的计算资源共享池来实现资源的虚拟化，以便于资源的调度[3]。云计算资源调度策略主要有：1) 以降低云计算数据中心的耗能为目的的调度策略；2) IBM开发出专用的资源监控代理和作业调度器实现云计算中资源的管理与调度。如IBM蓝云架构采用Tivoli系列产品[4]完成资源的管理与调度；3) 云计算大部分采用MapReduce[5]的编程模式作为一种任务调度模型。云计算根据网络资源的灵活性，是对网络资源进行外包的一种商业模型的创新[6]。
云计算中资源调度策略的引入，在一定程度上缓解了资源浪费以及不合理分配的问题，然而，对于所有资源的集中管理，云计算不能完美实现。SDN集中化的控制特点[7]可以在一定网络域内分域集中控制并整合所有网络资源，以便于资源的有效管理；其灵活的软件编程能力特点可以让非专业人员在调度策略中添加其他策略，进一步提高资源调度的性能；其高度的可扩展性特点可以解决业务需求快速增加而导致的资源调度效率低的问题。因此，在SDN体系机构背景下，系统就可以更加灵活地调度网络资源，更容易实现资源的定价以及交易管理。
拍卖[8]模型作为当前业界流行的市场机制之一，当同一商品被大量买家抢购时，一个最有效的方法就是提高价格，最终产生只有一个买家可以购买的结果[9]，可以确保最终定价的公平性以及最优性。所以，在SDN平台中设计一种只适合SDN服务的拍卖模型具有较大的实现意义。利用SDN架构的集中控制特点，将所有资源进行集中控制与管理，如资源的搜索、筛选以及组合，体现了SDN资源的多样性以及高可控性，因此SDN资源的配置以及价格的发现需要更复杂的拍卖算法来执行。
双向拍卖定价模型能够有效地解决交易过程中的垄断行为，但该定价方式仅仅适合对单一类型资源的交易，无法满足SDN环境下的海量资源的交易，导致效率降低；组合拍卖定价模型有效地避免了多种服务不能同时交易的问题，但是其着重于服务提供商ISP的利益最大化，从而无法满足SDN环境下用户和商家共同利益的情况；而组合双向拍卖不仅能够解决双向拍卖中的单一性问题，同时也能够满足SDN资源的多样性需求，再加上SDN的集中控制能力，使交易过程可以更有效地得到掌控，非常适用于SDN资源的配置以及价格的发现。
-
本节主要通过分析双向拍卖和组合双向拍卖定价算法，得出一种多归属的组合双向拍卖定价算法。网格环境与云环境中并不能充分实现这种双边市场的多归属性，但在SDN的分层架构中，层与层之间也存在着交易过程，每层之间的协商算法各不相同，最终协商出结果后，归纳到统一的平台进行交易，多归属性得到了充分的体现。
-
关于对双边市场的定义，不同学者从不同的角度进行了描述。从平台结构角度，文献[10]认为在双边市场中存在两种不同的用户，每一种用户通过市场中的平台与另一种用户进行交易，并在这一交易过程中获得利益，而平台起到一个Agent的作用。其次，从交叉网络外部性的角度，文献[11]认为如果在一个市场中，企业的用户分为“卖方”和“买方”两种类型，那么两种用户之间存在着交叉的网络外部性，并且企业通过某种策略吸引买卖双方的共同参与，可以使这种间接的网络外部性内在化，这就是双边市场。
从结构方面来说，双边市场主要分为：基本市场结构、平台互联互通和存在中间服务商的平台互联结构、存在中间服务提供商的结构以及消费者多归属结构[12]。本文主要利用消费者多归属特性，将整个SDN控制层分为多个单独的平台，其分层架构使得资源操作扩展到了多个平台中，消费者归属于不同的平台。类似于消费者多归属特性，本文认为服务提供商也具有多归属性，即消费者多归属性和提供商多归属性统称为多归属性。双边市场中的多归属不仅是确保交易过程中的冗余机制，还考虑到用户进行交易的客户的范围。
-
相对于SDN复杂的交易环境，网格环境相对简单。双向拍卖作为一种单一类型资源的拍卖定价方法，非常适合于网格环境。可以将其拍卖单一类型资源为依据，作为SDN服务交易过程中一种类型资源的定价算法，然后再结合其他定价算法得出一种仅仅适合于SDN环境下的定价算法。
文献[13]提出了一种典型的双向拍卖定价算法，主要针对网格资源的特点，从而实现网格资源的分配以及价格发现。
以m表示网络资源顾客的数量，n代表网络资源提供商的数量。其中顾客i对资源的需求量定义为Di，顾客总需求量D={D1，D2，…，Dm}，同时对单位资源的出价为bi。提供商j所提供的资源数量为Pj，提供商总供给量P={P1，P2，…Pn}，同时对单位资源的要价为aj。i和j分别满足∀i∈{1, 2, …，m}以及∀j∈{1, 2, …，n}。首先拍卖师对提供商的要价由低到高排序，不失竞价的公平性，设为：
$$ {a_n} > {a_{n - 1}} > \cdots > {a_1} $$ (1) 同理，对顾客的出价由高到低排序为：
$$ {b_1} > {b_2} > \cdots > {b_m} $$ (2) 根据上述对提供商要价降序和顾客出价升序的排列，可得到双方的交点O(q, p)。同时可以判定出交点O(q, p)有两种情况存在：
$$ \left\{ \begin{array}{l} {a_g} \ge {b_f} \ge {a_{g - 1}}\\ \mathop \sum \limits_{i = 1}^f {D_i} \ge \mathop \sum \limits_{j = 1}^{g - 1} {P_j} \ge \mathop \sum \limits_{i = 1}^{f - 1} {D_i} \end{array} \right. $$ (3) $$ \left\{ \begin{array}{l} {b_{f - 1}} \ge {a_g} \ge {b_f}\\ \mathop \sum \limits_{j = 1}^g {P_j} \ge \mathop \sum \limits_{i = 1}^{f - 1} {D_i} \ge \mathop \sum \limits_{j = 1}^{g - 1} {P_j} \end{array} \right. $$ (4) 根据式(1) 和式(2) 可以推断出，由交点O(q, p)的位置得出买卖双方交易的极限值f, g，其中卖方j满足j < g以及买方i满足i < f。卖方的成交开价定为交点O(q, p)两端纵坐标较小的一方，即Pa=min(ag, bf-1)。同理，买方的成交开价定为交点O(q, p)两端纵坐标较大的一方，即Pb=max(ag-1, bf)。最终，不论卖方还是买方的付费都在此区间内，得出最终交易价格。
由以上迭代过程可以看出此单一类型资源的双向拍卖存在以下缺陷：
1) 拍卖师对要价和出价的排序单一，没有考虑到其他排序方式。
2) 利益分配不均衡，买方的服务质量得不到保证。
3) 拍卖的目的仅仅是最大化卖方的收益。
4) 此类拍卖并不能跨平台运用，在SDN环境中难以发挥作用。
针对上述缺陷，文献[14]提出了一种适应性的云计算资源拍卖机制，保证了市场参与者的收益，同时考虑了多种意外情况下的拍卖过程。其定义了一种新的请求，即买方购买请求Bi和卖方出售请求S，满足Bi=(bi, Di), Sj=(aj, Pj)。为了保证参与者的收益，该拍卖模型采用以下策略：
1) 如果买方i交易成功，其收益pbi为：
$$ {\rm{p}}{{\rm{b}}_i} = ({v_i} - {b_i})D $$ (5) 式中，vi表示买方i消耗单位资源所得到的价值。若vi＞bi，则买方收益为正；若vi < vb，则买方收益为负；若vi=vb，则买方收益为零。
2) 如果卖方j交易成功，其收益psj为：
$$ {\rm{p}}{{\rm{s}}_j} = ({a_j} - {c_j}){P_j} $$ (6) 式中，cj表示卖方j提供单位资源所花费的成本。若cj＞aj，则卖方收益为负；若cj < aj，则卖方收益为正；若cj=aj，则卖方收益为零。
根据市场的供需关系，该拍卖模型给出了3种情况下的拍卖规则：1) 供大于求P > D；2) 供不应求P < D；3) 供需平衡P=D。
上述双向拍卖过程主要存在以下缺陷：
1) 双向拍卖模型是对单一类型资源的拍卖，不存在资源组合的功能。
2) 资源价格是在价值上上下波动的，不会有太大的偏差。
3) 在供需平衡状态下，该拍卖模型是在供不应求和供大于求两种规则下，挑选其中交易量最大的一种规则。这种情况下，拍卖代理仅仅是确保了双方的利益，并没有在此基础上最大化双方的利益。
上述模型仅仅是对单一资源的拍卖，而在当前复杂的网络环境中已经不再适用。
-
组合拍卖充分考虑了多类资源同时交易的问题，考虑的较为全面，不仅解决了双向拍卖的资源单一性，而且又满足了交易双方共同的利益。针对传统拍卖的垄断性、双向拍卖的单一性以及组合拍卖的服务商利益唯一性等缺点，文献[15]给出了一种针对网格环境下资源定价以及分配的组合双向拍卖定价模型。该模型主要将整个网格环境分为4个部分：用户代理、网格服务提供商、网格信息业务以及网格市场拍卖代理。
首先定义一个通用的组合双向拍卖模型：设集合G中含有k种不同类型的资源。参与拍卖的人数(主要包括顾客和提供商)为m，所拍卖的服务集合S = {S1, S2, …, Sm}，其中，Sj=(nj, pj)，nj=(n1j, n2j, …, ngj)，nij代表集合S中第j个参拍服务中的第i类资源的数量，pj代表参拍人j对该资源组合(服务)的报价，pj < 0表示提供商的要价，pj＞0表示顾客的出价。同时，考虑到资源供需情况的变化，nij < 0代表对资源i的供给；nij＞0代表对资源i的需求；nij=0代表资源i不在所拍卖的服务集合中。则可以得出一种通用的组合双向拍卖模型为：
$$ \max \mathop \sum \limits_{j = 1}^m {p_j}{x_j} $$ (7) $$ ({\rm{PM}})\mathop \sum \limits_{j = 1}^m {n_{ij}}{x_j} \le {\rm{0}}\;\forall i \in G $$ (8) $$ {x_j} \in \{ 0,1\} \;\forall j \in \{ 1,2, \cdots ,m\} $$ (9) 根据式(7) 可以看出该通用模型是以最大化市场交易数量为目的，式(8) 为限制条件。根据供需变化情况1)，当顾客竞买某些服务时，资源提供商必须能够提供该数量的服务。式(9) 表示一种0-1规划模型，将整个组合双向拍卖模型的复杂度降低。
网格环境下的组合双向拍卖过程主要存在以下缺陷：1) 上述交易模型是在网格环境下搭建的，在该环境下，对于资源组合的问题，系统并不能对资源进行任意地组合。2) 网格计算类似于传统网络，其对资源的“掌控能力”并不强烈，不能同时保证双方的利益。3) 对于资源的组合问题，网格计算相对于云计算等环境仍然存在差距。
基于上述模型，文献[16]将此组合双向拍卖模型应用到了云计算中。云计算将所有资源虚拟化、池化，大大提升了资源的可塑性，即组合性。主要不同的是，采用文献[17]中的K-定价方案得出云环境下的交易价格矩阵T(e, f)，其含义是排序Dl中顺序为e的用户Dl(e)与排序Ul中的顺序为f的云计算服务提供商Ul(f)交易时的价格矩阵：
$$ \begin{array}{l} \boldsymbol{T}(e,f) = K{\boldsymbol{{\rm{ap}}}_{{\rm{Dl}}(e)}} + (1 - K){\boldsymbol{{\rm{ap}}}_{{\rm{Ul(}}f{\rm{)}}}}\\ K \in (0,1) \end{array} $$ (10) 式中，apDl(e)表示用户Dl(e)的价格矩阵；apU1(f)为云计算服务提供商U1(f)的价格矩阵。
为了计算简便，令K=1/2，含义就是将整个云市场的盈余平均分配给交易双方，以达到刺激消费的目的。
-
业界大部分文献通常利用某种拍卖算法将整个交易过程人为地进行分层或市场化，并没有考虑其所利用的架构是否适合这种分层。对于SDN架构而言，其本质就是分层的，不会有将交易过程分层而存在不兼容的问题。
-
服务链[18]指一个或多个服务相互链接在一起并且共同运行的一种功能。在传统网络的物理层中，早已存在服务链，但传统网络的服务链和网络设备是紧密耦合的，部署也比较复杂，所以当服务链拓展时，需要改变整个拓扑以及重新配置网络设备。
在SDN体系架构中，某些元素(包括路由器)可以作为虚拟机在服务器上运行，对这些元素的需求可以根据服务的要求进行调整，这些都是在SDN控制器的控制下进行的。由SDN服务链完成配置，这些元素都按照某种逻辑链接在一起形成一种服务链。所以，当前的服务链默认为是SDN服务链。因此本文将这些SDN元素统一定义为SDN资源，不同类型的SDN资源链接在一起形成一种资源组合服务链，从而完成某一种特定的服务功能。
-
SDN从分层的角度，诠释了未来网络架构的特性。顾客、服务提供商、拍卖代理以及拍卖平台层次分明。如果将组合双向拍卖模型应用于其他网络中，不仅不能达到资源优化、节省的效果，反而会进一步加重网络的负担。SDN的分层架构，可以将4种角色完美地集成到每一层之中，这样就形成了一种层与层之间的SDN平台价格协商算法。
此外，考虑到最大化交易双方的利益，本文将资源交易的平台扩展为一种基于多归属结构的SDN资源交易模型。
如图 1所示，本文根据SDN的三层架构，提出一种新型的多归属组合双向拍卖模型(multi-homing combinatorial double auction model, MCDAM)。不同于传统组合双向拍卖模型，在SDN环境下，3类市场参与者是分层的，彼此之间的交流通过特殊的协议完成，因此它们之间既是相互独立又紧密联系。应用层中有许多用户，用户之间是相互独立的，它们归属于不同的平台。控制层中存在多个平台，平台两端分别连接着不同的用户和提供商，多个平台的存在解决了单一平台时的垄断性以及用户和提供商选择单一型的问题。转发层中有众多提供商加盟，它们为各个平台提供不同类型的资源。
图 1 多归属组合双向拍卖模型
双边多归属体现现在企业之间的关系，以中国铁路为例，现有的支付方式有工商网银、支付宝，若不考虑企业竞争，理论上也可以使用微信、京东支付、易付宝等。可以看出中国铁路的用户是隶属于不同的支付平台的，同时，每个平台都依赖于不同的移动运营商。
-
MCDAM算法的思想在于：每个节点(包括用户和提供商)向隶属于交易平台的资源代理(resource broker, RB)提供服务链，每条链中都携带这对资源的需求以及供给，其目的主要是向市场传递自己的交易信息。在提供的过程中，节点仅仅是以各自的代理去传递的，因此此时不存在用户和提供商的概念。RB的功能之一就是将服务链拆解，并分类为买方和卖方。
假设SDN资源系统有n个节点，k种资源。服务链可以表示为一个二元集合(qj, pj)，主要包含一个多归属组合资源价格包和一个多归属组合资源数量包，其中j满足j={1, 2, …，n}；多归属组合资源价格链为pj={p1j, p2j, …，pkj}，其中pij代表节点j上i类资源的价格，该价格链均为一个由正数组成的集合；qj代表对资源的需求情况，且满足qj={q1j, q2j, …，qkj}。若qij为正，则代表节点j为买方且需要i类资源；若qij为负，则代表节点j为卖方且提供i类资源；若qij为零，则代表节点j并没有需求或者供给，类似于供需平衡。由上述可得多归属组合资源服务链qj包含正数、负数和零集合。
下面给出基于SDN平台的价格协商算法的迭代过程：
1) RB向整个SDN环境发布竞价开始，整个系统中的节点向RB发送多归属服务链(multi-homing service chain, MSC)，随后RB将MSC拆解成购买和出售两种类型的服务链，同时保留那些供需平衡(qij=0) 的服务链。
2) 根据通用组合双向拍卖模型，即式(11) 求出满足市场利益最大化的节点，同时还要保证需求都能得到供给。然后，RB将购买类型的节点统一存放到序列表Bl中，将出售类型的节点统一存放到序列表Sl中，将供需平衡的节点统一存放到序列表Hl中。可能会存在某些即充当卖方又充当买方的节点，因此Sl和Bl中肯定有重复的节点：
$$ \begin{array}{l} \max \mathop \sum \limits_{j = 1}^m {p_j}{x_j}({\rm{PM}})\mathop \sum \limits_{j = 1}^m {q_{ij}}{x_j} \le {\rm{0}}\;\forall i \in G{\rm{}}\\ {x_j} \in \{ 0,1\} \forall j \in \left\{ {1,2, \cdots ,m} \right\} \end{array} $$ (11) 3) 以资源类型i为例，资源代理将购买序列表Bl中的节点按照价格pij降序排列，得到一个新的序列表DBi并将其对应的资源需求的出价pij存放到UBi中，对应的资源需求的数量qij存放到NBi中；然后，将出售序列表Sl中的节点按照价格pij升序排列，得到一个新的序列表US1i并将其对应的资源提供的要价pij存放到USi中，对应的资源提供的数量qij存放到NSi中。
4) 根据上述的排序方法，可以得到一个交易的平均定价矩阵ap(u, v)，其含义代表用户代理平均价格序列表中的第u个用户同SDN服务提供商平均价格序列表中的第v个提供商交易过程中的平均价格。
5) 利用K-定价方案计算得到SDN环境下的交易价格矩阵T(u，v)，其含义是降序排列DBl中的顺序为u的用户DB1u与升序排序USl中的顺序为v的SDN服务提供商US1v交易时的价格矩阵。计算如下：
$$ \boldsymbol{T}(u,v) = K{\boldsymbol{{\rm{ap}}}}_{{\rm{DBl}}_u} + (1 - K){\boldsymbol{{\rm{ap}}}}_{{\rm{USl}}_v}K \in (0,1) $$ (12) 6) 以资源类型i为例，序列表DB1i中的第一个节点B1和序列表US1i中的第一个节点S1交易，判断此节点的交易数量是否满足买家的需要数量。其一，若S1能够满足买家B1的需求，且B1与S1交易之后节点S1还有剩余的资源，则让序列表DB1i中的第二个节点B2继续与节点S1交易；若S1能够满足买家B2的需求，且B2与S1交易之后节点S1剩余的资源数量刚好等于零，则让序列表DB1i中的第二个节点B2与序列表US1i中的第二个节点S2交易。其二，若S1不能够满足买家B1的需求，代表节点S1提供量不足，则让节点B1与S1交易之后再与序列表US1i中的第二个节点S2交易。一直到资源i买卖结束，才能进行下一类型资源i+1的交易。
根据以下算法对资源进行定价：
1) 初始化资源种类i、多归属服务链的买家和卖家x, y以及UBi中第x个买家和USi中第y个卖家对资源i的交易数量Qi=(x, y)和交易价格Pi=(x, y)。
即i=1, x=1, y=1, Qi=(x, y)=[], Pi=(x, y)=[]。
2) 查看两节点之间的交易情况。
① 供大于需NSi(v)＞NBi(u)：新的交易数量为初始化交易数量(Qi=(x, y)=[])与买家需求之和，即，Qi=(x, y)=Qi=(x, y)+NBi(u)；新的交易价格矩阵为初始化价格矩阵与买家需求和平均价格之积的和，即Pi(x, y)=Pi(x, y)+ap(u, v)NBi(u)；新的提供商供应量变为初始化供应量与用户需求之差，即，NSi(v)=NSi(v)-NBi(u)；此时，则该用户需求得到满足，不再需要资源，即NBi(u)；执行步骤3)。
② 供不应求NSi(v) < NBi(u)：新的交易数量为初始化交易数量(Qi=(x, y)=[])与提供商供应量之和，即，Qi=(x, y)=Qi(x, y)+NSi(v)。
新的交易价格为初始化交易价格与供应量和平均价格之积的和，即Pi(x, y)=Pi(x, y)+ap(u, v)NSi(v)；新的用户需求为初始化需求与供应量之差，即，NBi(u)=NBi(u)-NSi(v)；此时，则该提供商的供应量全部供给用户，没有剩余，即NSi(v)=0；执行步骤4)。
③ 供需平衡NSi(v)=NBi(u)：即T(u, v)=KapDB1u+(1-K)apUS1v；此时供需平衡，为了增加双方得收益，令K=1/2，就是将整个云市场的盈余平均分配给交易双方；结束。
3) 第u个用户对i类型资源的需求得到满足之后，储存当前交易的数量Qi(x, y)以及价格Pi(x, y)z，并且若资源提供商提供的资源没有剩余，则交易结束，若还有剩余，则对下一个资源请求用户(u=u+1) 继续迭代，跳往步骤2)。
4) 第v个提供商对i类型资源全部供给之后，储存当前交易的数量Qi(x, y)以及价格Pi(x, y)。若资源请求方得到满足，则交易结束，若还有需求，则对下一个资源提供商(v=v+1) 继续迭代，跳往步骤2)。
7) 经过上述迭代可以得到，第x个用户买进资源i的花费OBi(x)以及第y个提供商供给资源i的收入OSi(y)。
$$ {\rm{O}}{{\rm{B}}_i}(x) = \mathop \sum \limits_{x = 1}^m {P_i}(x,y){\rm{O}}{{\rm{S}}_i}(y) = \mathop \sum \limits_{y = 1}^{n - m} {P_i}(x,y) $$ (13) 并由资源i的收入情况可以得到k种资源的全部收入，即：
$$ {\rm{OB}}(x) = \mathop \sum \limits_{i = 1}^k {\rm{O}}{{\rm{B}}_i}(x){\rm{OS}}(y) = \mathop \sum \limits_{i = 1}^k {\rm{O}}{{\rm{S}}_i}(y) $$ (14) -
在效用方面而言，为了详细地分析基于SDN平台的价格协商算法在效用方面的特色，下面给出14个节点的资源供需情况。其中，为体现交易的无差别性，资源的价格/效用等信息均采用了无量纲。仿真参数如下：1) 14个SDN节点，7个用户以及7个提供商；2) A、B、C 3种资源进行交易；3) 对A、B、C 3类资源的报价范围分别取：70~90、10~25、155~195之间均匀分布的整数值。
表 1代表 14个节点对A、B、C 3种资源的供需情况，其中数字大于零代表用户提出需求，小于零代表提供商提出供给。如对于A资源，节点1、2、4、7、8、10、13的用户提出需求，其余为提供商提出供给。表 2代表 14个节点对A、B、C 3种资源的要价出价情况。如果节点代表用户，则表示对该资源的出价p > 0，n > 0；如果节点代表提供商，则代表对该资源的要价p < 0，n < 0。
表 1 节点资源供需
资源 节点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A 3 1 -2 1 -1 -2 2 3 -1 1 -2 -3 2 -2 B 1 -3 -2 3 1 -2 2 1 -1 1 -2 -1 2 -1 C 2 3 -2 1 -1 2 1 -2 -3 -3 -1 0 1 3 表 2 节点资源报价
价格 节点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 PA 86 76 -75 92 -72 -80 87 83 -77 78 -69 -70 81 -78 PB 18 -14 -10 16 19 -13 21 15 -11 8 -9 -16 13 -17 PC 187 192 -158 182 -165 183 172 -155 -172 -182 -169 174 175 179 根据资源的类型将A、B、C 3种资源分为买家和卖家的情况：1) 买家出价降序排列；2) 卖家要价升序排列如表 3~表 8所示。
表 3 A资源买家出价降序排列
节点编号 4 7 1 8 13 10 2 A需求量 1 2 3 3 2 1 1 买家出价 92 87 86 83 81 78 76 交易价格 80.5 78/78.5 78/78/79 79/79/80 79.5 79 78 交易平均价格 80.5 78.25 78.3 79.3 79.5 79 78 买家效用 11.5 8.75 7.7 3.7 1.5 -1 -2 表 4 A资源卖家要价升序排列
节点编号 11 12 5 3 9 14 6 A供给量 -2 -3 -1 -2 -1 -2 -2 卖家要价 -69 -70 -72 -75 -77 -78 -80 交易价格 80.5/78 78.5/78/78 79 79 80 79.5 79/78 交易平均价格 79.25 78.2 79 79 80 79.5 78.5 卖家效用 10.25 8.2 7 4 3 1.5 -1.5 表 5 B资源买家出价降序排列
节点编号 7 5 1 4 8 13 10 B需求量 2 1 1 3 1 2 1 买家出价 21 19 18 16 15 13 8 交易价格 15 14.5 14 13.5/14.5/14.5 14.5 13.5 12 交易平均价格 15 14.5 14 14.2 14.5 13.5 12 买家效用 6 4.5 4 1.8 0.5 -0.5 -4 表 6 B资源卖家要价升序排列
节点编号 11 3 9 6 2 12 14 B供给量 -2 -2 -1 -2 -3 -1 -1 卖家要价 -9 -10 -11 -13 -14 -16 -17 交易价格 15 14.5/14 13.5 14.5 14.5/13.5/13.5 12 \ 交易平均价格 15 14.25 13.5 14.5 13.8 12 \ 卖家效用 5 4.25 2.5 1.5 -0.2 -4 \ 表 7 C资源买家出价降序排列
节点编号 2 1 6 4 14 13 7 C需求量 3 2 2 1 3 1 1 买家出价 192 187 183 182 179 175 172 交易价格 173.5/173.5 /175 175.5/176 176/177.5 177 175.5/180.5 /180.5 178.5 \ 交易平均价格 174 175.75 176.75 177 178.8 178.5 \ 买家效用 18 11.25 6.25 5 0.2 -3.5 \ 表 8 C资源卖家要价升序排列
节点编号 8 3 5 11 9 12 10 C供给量 -2 -2 -1 -1 -3 0 -3 卖家要价 -155 -158 -165 -169 -172 -174 -182 交易价格 173.5 175 /172.5 176 176 176.5/177 /175.5 \ 180.5/180.5/ 178.5 交易平均价格 173.5 173.75 176 176 176.7 \ 179.8 卖家效用 18.5 15.75 11 7 4.7 \ -2.2 A、B、C 3种资源根据基于SDN平台的价格协商算法可以分别得出其交易的最优价格。采用MCDAM方法概述了某一时刻SDN市场的全部资源，这样使得出价较高的用户和出价低的提供商都可以获得较高的效用。
目前业界对SDN网络资源定价算法的研究较欠缺，本文给出本算法对14个节点的出价与效用的仿真结果。效用是经济参与者对某次交易满足的一个度量，因此引入效用来分析各个节点之间的交易过程。下面将分别对A、B、C 3种资源进行资源出价与最终交易效用进行比对分析，并得出3种资源出价与交易效用的效果图，如图 2~图 4所示。
图 2 A资源各个节点的出价与效用
图 3 B资源各个节点的出价与效用
图 4 C资源各个节点的出价与效用
由图 2~图 4可知，买家的出价严格按照降序排序，卖家的要价按照升序排序，这符合MCDAM的价格排序方式。采用多归属交易方式，揭示了所有的SDN资源，对于买家而言，出价越高，其交易效用就越高，而卖家正好相反。如图 3所示，买家节点10、2，卖家节点6出现负的效用，这是因为买家出价太低，而卖家的要价太高所导致的。这些节点可以继续交易，继续交易可能会导致节点信任度下降，被系统判定为恶意节点；也可以放弃交易，并在下一轮重新竞拍。这种方式可以刺激整体的消费水平，从而使SDN平台处于一个稳定的市场环境下。
-
本文利用市场机制研究网络资源的定价与分配问题，提出将整个SDN资源经济学模型集成到SDN的三层架构中，完成资源交易的建模问题。本文首先介绍了学术界流行的拍卖模型，得出只有组合双向拍卖才能应用于复杂的SDN交易环境的结论。然后根据双向拍卖、组合拍卖以及组合双向拍卖模型的优点，结合SDN体系架构的特点提出一种适用于SDN分层架构的MCDAM算法，并对该算法进行了一定的数据分析。证明了该算法的可行性以及稳定性，并可以有效缓解SDN资源面临的问题。
SDN Resources Price Negotiation Algorithm Based on Multi-Homing Combinatorial Double Auction Model
-
摘要: 软件定义网络（SDN）作为一种新型的网络体系架构，打破了传统网络的封闭模式，实现了控制与转发分离，可以有效地解决当前互联网的一系列问题。为了实现SDN网络资源的合理分配，该文提出利用经济学原理来抑制SDN网络资源的浪费。根据当前业界流行的拍卖模型的特性，提出一种适用于SDN环境下的价格协商算法，即多归属组合双向拍卖模型（MCDAM）算法，解决了资源买卖双方交易价格是否合理的问题，达到以价格为杠杆实现SDN资源的合理分配的目的，并通过仿真实验证明了该算法的优越性以及可行性。Abstract: As a new type of network architecture, software defined network (SDN) breaks the closed mode of traditional network, realizes the separation between forwarding and control, and therefore can effectively solve a series of problems of the current Internet. Taking advantage of economic principles and according to the characteristics of the traditional auction model, we propose a price negotiation algorithm, namely multi-homing combinatorial double auction model (MCDAM) algorithm, to curb the waste of SDN resources. MCDAM can solve the problem of reasonable transaction price between the buyers and sellers, make the price as a lever to achieve the purpose of SDN resources reasonable allocation. Simulation results illustrate the superiority and feasibility of the proposed algorithm.
-
Key words:
- auction model /
- multi-homing /
- network resources /
- price negotiation /
- SDN
-
表 1 节点资源供需
资源 节点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A 3 1 -2 1 -1 -2 2 3 -1 1 -2 -3 2 -2 B 1 -3 -2 3 1 -2 2 1 -1 1 -2 -1 2 -1 C 2 3 -2 1 -1 2 1 -2 -3 -3 -1 0 1 3 
下载: 导出CSV
表 2 节点资源报价
价格 节点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 PA 86 76 -75 92 -72 -80 87 83 -77 78 -69 -70 81 -78 PB 18 -14 -10 16 19 -13 21 15 -11 8 -9 -16 13 -17 PC 187 192 -158 182 -165 183 172 -155 -172 -182 -169 174 175 179
下载: 导出CSV
表 3 A资源买家出价降序排列
节点编号 4 7 1 8 13 10 2 A需求量 1 2 3 3 2 1 1 买家出价 92 87 86 83 81 78 76 交易价格 80.5 78/78.5 78/78/79 79/79/80 79.5 79 78 交易平均价格 80.5 78.25 78.3 79.3 79.5 79 78 买家效用 11.5 8.75 7.7 3.7 1.5 -1 -2
下载: 导出CSV
表 4 A资源卖家要价升序排列
节点编号 11 12 5 3 9 14 6 A供给量 -2 -3 -1 -2 -1 -2 -2 卖家要价 -69 -70 -72 -75 -77 -78 -80 交易价格 80.5/78 78.5/78/78 79 79 80 79.5 79/78 交易平均价格 79.25 78.2 79 79 80 79.5 78.5 卖家效用 10.25 8.2 7 4 3 1.5 -1.5
下载: 导出CSV
表 5 B资源买家出价降序排列
节点编号 7 5 1 4 8 13 10 B需求量 2 1 1 3 1 2 1 买家出价 21 19 18 16 15 13 8 交易价格 15 14.5 14 13.5/14.5/14.5 14.5 13.5 12 交易平均价格 15 14.5 14 14.2 14.5 13.5 12 买家效用 6 4.5 4 1.8 0.5 -0.5 -4
下载: 导出CSV
表 6 B资源卖家要价升序排列
节点编号 11 3 9 6 2 12 14 B供给量 -2 -2 -1 -2 -3 -1 -1 卖家要价 -9 -10 -11 -13 -14 -16 -17 交易价格 15 14.5/14 13.5 14.5 14.5/13.5/13.5 12 \ 交易平均价格 15 14.25 13.5 14.5 13.8 12 \ 卖家效用 5 4.25 2.5 1.5 -0.2 -4 \
下载: 导出CSV
表 7 C资源买家出价降序排列
节点编号 2 1 6 4 14 13 7 C需求量 3 2 2 1 3 1 1 买家出价 192 187 183 182 179 175 172 交易价格 173.5/173.5 /175 175.5/176 176/177.5 177 175.5/180.5 /180.5 178.5 \ 交易平均价格 174 175.75 176.75 177 178.8 178.5 \ 买家效用 18 11.25 6.25 5 0.2 -3.5 \
下载: 导出CSV
表 8 C资源卖家要价升序排列
节点编号 8 3 5 11 9 12 10 C供给量 -2 -2 -1 -1 -3 0 -3 卖家要价 -155 -158 -165 -169 -172 -174 -182 交易价格 173.5 175 /172.5 176 176 176.5/177 /175.5 \ 180.5/180.5/ 178.5 交易平均价格 173.5 173.75 176 176 176.7 \ 179.8 卖家效用 18.5 15.75 11 7 4.7 \ -2.2
下载: 导出CSV
-
[1] Cisco. Cisco visual networkingindex:Global mobile data traffic forecast update, 2013-2018[EB/OL].[2015-12-23]. http://www.cisco.com/c/dam/en/us/solutions/collateral/service-provider/global-cloud-index-gci/white-paper-c11-738085.pdf?referring_site=RE&pos=3&page=http://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/mobile-white-paper-c11-520862.html. [2] 曹礼财.搜索框的营销疆界-赢时代全球搜索引擎营销大会在沪召开[J].市场观察, 2012(1):82-83. http://www.cnki.com.cn/Article/CJFDTOTAL-SCGC201201045.htm CAO Li-cai. The marketing boundaries of the search boxglobal search engine marketing conference of win era held in Shanghai[J]. Market Observer, 2012(1):82-83. http://www.cnki.com.cn/Article/CJFDTOTAL-SCGC201201045.htm [3] 林伟伟, 齐德昱.云计算资源调度研究综述[J].计算机科学, 2012, 39:1-6. http://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201210002.htm LIN Wei-wei, QI De-yun. Survey of resource scheduling in cloud computing[J]. Computer Science, 2012, 39:1-6. http://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201210002.htm [4] HAWKINS L. IBM'S Tivoli systems[R]. Corporate Meetings and Incentives.[S.l.]:Betascript Publishing, 2002, 21(3):13. [5] SCHMIDT K J, CHRISTOPHER P.弹性MapReduce编程[M].北京:中国电力出版社, 2015:23-25. SCHMIDT K J, CHRISTOPHER P. Programming elastic MapReduce[M]. Beijing:China Electric Power Press, 2015:23-25. [6] ABBOTT M L, FISHER M T. The art of scalability-scalable web architecture, processes and organizations for the modem enterprise[M].[S.l.]:Addison-Wesley Professional, 2009. [7] 宋海权, 郭进, 侯孟书, 等.基于网络时延的SDN逻辑一致性策略研究[J].电子科技大学学报, 2014, 43(5):730-735. http://www.juestc.uestc.edu.cn/CN/abstract/abstract483.shtml SONG Hai-quan, GUO Jin, HOU Meng-shu, et al. Research on the SDN consistency problems of the control logic based on network delay[J]. Journal of University of Electronic Science and Technology of China, 2014, 43(5):730-735. http://www.juestc.uestc.edu.cn/CN/abstract/abstract483.shtml [8] 陈绍刚, 赵蜀蓉.基于随机估值的两物品拍卖的投标决策[J].电子科技大学学报, 2002, 31(4):418-421. http://www.cnki.com.cn/Article/CJFDTOTAL-DKDX200204019.htm CHENG Shao-gang, ZHAO Shu-rong. Study on bidding decision making of two-object auction based on random estimate[J]. Journal of University of Electronic Science and Technology of China, 2002, 31(4):418-421. http://www.cnki.com.cn/Article/CJFDTOTAL-DKDX200204019.htm [9] 马俊.拍卖模型及其应用研究[M].北京:中国财政经济出版社, 2004:5-11. MA Jun. Auction model and the application research[M]. Beijing:China Financial & Economic Publishing House, 2004:5-11. [10] WRIGHT J. The determinants of optimal interchange fees in payment systems[J]. Journal of Industial Economics, 2004, 52(1):1-26. doi: 10.1111/j.0022-1821.2004.00214.x [11] 罗亮. 网络融合趋势下电信业市场结构商业模式与公共政策的经济分析[D]. 南京: 东南大学, 2005. http: //cdmd. cnki. com. cn/Article/CDMD-10286-2007064284. htm LUO Liang. Business model of Telecom market structure under network convergenceand the economic analysis of public policy[D]. Nanjing:Southeast University, 2005. http: //cdmd. cnki. com. cn/Article/CDMD-10286-2007064284. htm [12] 诸葛斌, 邓丽, 戴国伟, 等.基于双边市场多归属结构的SDN资源管理机制[J].电信科学, 2014, 30(5):55-64. http://www.cnki.com.cn/Article/CJFDTOTAL-DXKX201405010.htm ZHU Ge-bin, DENG Li, DAI Guo-wei, et al. SDN resource management mechanism based on bilateral market's multi-homing architecture[J]. Telecommunications Science, 2014, 30(5):55-64. http://www.cnki.com.cn/Article/CJFDTOTAL-DXKX201405010.htm [13] 翁楚良, 陆鑫达.一种基于双向拍卖机制的计算网格资源分配方法[J].计算机学报, 2006, 29(6):1004-1008. http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX200606020.htm WENG Chu-liang, LU Xin-da. A double auction method for resource allocation on computational grids[J]. Chinese Journal of Computers, 2006, 29(6):1004-1008. http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX200606020.htm [14] 丁丁, 罗四维, 艾丽华.基于双向拍卖的适应性云计算资源分配机制[J].通信学报, 2012(S1):132-140. http://www.cnki.com.cn/Article/CJFDTOTAL-TXXB2012S1016.htm DING Ding, LUO Si-wei, AI Li-hua. Adaptive double auction mechanism for cloud resource allocation[J]. Journal on Communications, 2012(S1):132-140. http://www.cnki.com.cn/Article/CJFDTOTAL-TXXB2012S1016.htm [15] 李立, 刘元安, 马晓雷.基于组合双向拍卖的网格资源分配[J].电子学报, 2009, 37(1):165-169. http://cdmd.cnki.com.cn/Article/CDMD-10013-1012499249.htm LI Li, LIU Yuan-an, MA Xiao-lei. Gridresource allocation based on the combinatorial double auction[J]. Acta Electronica Sinica, 2009, 37(1):165-169. http://cdmd.cnki.com.cn/Article/CDMD-10013-1012499249.htm [16] 谢剑. 云计算服务产品的组合双向拍卖模型研究[D]. 杭州: 浙江工商大学, 2013. http: //cdmd. cnki. com. cn/Article/CDMD-10353-1013185579. htm XIE Jian. Study on TEH model of combinatorial double auction for the cloud computing services and products[D]. Hangzhou:Zhejiang Gongshang University, 2013. http: //cdmd. cnki. com. cn/Article/CDMD-10353-1013185579. htm [17] SHOHAM Y, LEYTONB K. Multi-agent systems:Algorithmic, game-theoretic, and logical foundations[M]. Cambridge:Cambridge University, 2008:5929-5934. [18] 胡正华, 宁宣熙.服务链概念、模型及其应用[J].商业研究, 2003(7):111-114. http://www.cnki.com.cn/Article/CJFDTOTAL-BUSI200307039.htm HU Zheng-hua, NING Xuan-xi. Service chain concept, model and application[J]. Commercial Research, 2003(7):111-114. http://www.cnki.com.cn/Article/CJFDTOTAL-BUSI200307039.htm -
点击查看大图
图(4) / 表(8)
计量
- 文章访问数: 3872
- HTML全文浏览量: 1251
- PDF下载量: 198
- 被引次数: 0
