北京邮电大学学报

  • EI核心期刊

北京邮电大学学报 ›› 2024, Vol. 47 ›› Issue (5): 22-28.

• 论文 • 上一篇    下一篇

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

张桂玉1,白露莹1,牛佳宁2,郑羽欣1,邓木明1   

  1. 1. 中讯邮电咨询设计院有限公司
    2. 国家电网有限公司信息通信分公司
  • 收稿日期:2023-09-26 修回日期:2024-01-23 出版日期:2024-10-28 发布日期:2024-11-10
  • 通讯作者: 张桂玉 E-mail:zhanggy@dimpt.com

Combination Auction-based Online Scheduling for the Deterministic IP Networks

  • Received:2023-09-26 Revised:2024-01-23 Online:2024-10-28 Published:2024-11-10

摘要: 确定性IP(DIP,deterministic IP)技术通过节点之间的频率同步,提高了网络的可扩展性。然而,频率同步带来更复杂的转发模型,引入了非凸、不可微分的运算,增加了调度问题的复杂性。目前,大多数调度方案仍然依赖离线机制或在线贪婪机制,导致算法复杂度较高或者无法保证后到达重要时敏业务的接入。为解决上述问题,提出了一种基于组合拍卖的在线调度算法,将网络资源视为物品、网络本身视为拍卖者、业务流视为竞标者。在所有时间敏感流到达之前,提前完成带有非凸、不可微分运算的离线资源枚举操作。当网络开始工作时,只需从可行集合中选择一组资源,分配给新到达的时敏业务,从而降低在线部分的计算复杂度。同时,基于组合拍卖框架,设计了线性递增的资源定价函数,确保重要的时敏业务有机会可以被准入网络。最后,通过仿真实验,证明了所提算法能够在大规模网络中为关键时敏业务提供高效的传输服务。

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

Abstract: Deterministic IP (DIP) networking uses frequency synchronization to improve the network scalability. However, frequency synchronization introduces a more complex forwarding model, involving non-convex and non-differentiable operations, which increases the complexity of scheduling problems. Moreover, most scheduling schemes still rely on online heuristic algorithms and offline mechanisms, leading to either inefficient scheduling performance or high computational complexity. To address these issues, an online flow scheduling algorithm is proposed based on the combinatorial auction, where the resources are items, the flows are bidders, and the network is the auctioneer. Non-differential operations are carried out during the bundle enumeration phase before the flows arrive. When they arrive, TS flows only need to select a resource bundle from the feasible set. Additionally, we carefully design the resource’s pricing function which is a linear increasing function. The important time-critical applications could still access to the network even if they come latter. Finally, we conduct simulations that demonstrate the effectiveness of the proposed algorithm.

Key words: deterministic DIP (DIP) networking, online flow scheduling, auction theory

中图分类号: