基于组合拍卖的确定性IP网络在线调度机制  

Combination Auction-Based Online Scheduling for the Deterministic IP Networks

作　　者：张桂玉[1] 白露莹 牛佳宁 郑羽欣 邓木明 ZHANG Guiyu;BAI Luying;NIU Jianing;ZHENG Yuxin;DENG Muming(China Information Technology Designing&Consulting Institute Company Limited,Beijing 100048,China;Information and Communication Branch of State Grid Corporation of China,Beijing 100761,China)

机构地区：[1]中讯邮电咨询设计院有限公司,北京100048 [2]国家电网公司信息通信分公司,北京100761

出　　处：《北京邮电大学学报》2024年第5期22-28,共7页Journal of Beijing University of Posts and Telecommunications

摘　　要：用确定性IP网络可通过节点间的频率同步,提升网络的扩展能力。然而,频率同步引入了更复杂的转发模型,伴随着非凸、不可微分的运算,增加了调度问题的复杂性。目前,大多数调度方案仍然依赖离线机制或在线贪婪机制,这不仅使算法的复杂度变高,还难以保障后续到达的重要时敏业务的接入。为了解决这些问题,提出了一种基于组合拍卖的在线调度算法,将网络资源视为拍卖物品,网络则充当拍卖者,而将业务流作为竞标者。在所有时敏流到达之前,先行完成含非凸、不可微分运算的离线资源枚举操作。当网络投入运行时,只需从预先计算的可行集合中挑选资源,分配给新到达的时敏业务,降低了在线部分的计算复杂度。同时,基于组合拍卖的框架,设计了线性递增的资源定价函数,确保重要时敏业务能够获得网络接入机会。仿真实验结果表明,所提算法在大规模网络中能够为重要的时敏业务提供高效的传输服务。Deterministic Internet protocol(IP)networking uses frequency synchronization to improve the network scalability.However,frequency synchronization introduces a more complex forwarding model,accompanied by non-convex and non-differentiable operations,which increases the complexity of scheduling problems.Moreover,most scheduling schemes still rely on offline mechanisms or online greedy mechanisms,which not only make the algorithm complex,but also difficult to ensure the access of important time-sensitive services that arrive in the future.To address these issues,an online flow scheduling algorithm is proposed based on the combinatorial auction,where network resources are auction items,the flows are bidders,and the network is the auctioneer.Before all time-sensitive streams arrive,it is necessary to complete the offline resource enumeration operation with non-convex and non-differentiable operations.When the network is put into operation,it only needs to select resources from the pre-calculated feasible set to allocate to the newly arrived time-sensitive services,which reduces the computational complexity of the online part.Meanwhile,based on the framework of combinatorial auction,a linearly increasing resource pricing function is designed to ensure that key time-sensitive services can obtain network access opportunities.Finally,simulation experiments show that the proposed algorithm can provide efficient transmission services for important time-sensitive services in large-scale networks.

关 键 词：确定性IP网络 在线流量调度 拍卖理论 

分 类 号：TN915.41[电子电信—通信与信息系统]