A Study on Autonomous Routing Schemes for Multiplexed Networks with Instable Bandwidths

带宽不稳定复用网络自主路由方案研究

• 批准号: 13680417
• 负责人: FUJITA Satoshi
• 金额: $ 2.18万
• 依托单位: Hiroshima University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680417/
• 关键词: Routing; Resource Allocation; Dynamic Network; Optimal Routes; Load Balancing; Multiplexed Networks; 多重化ネットワーク

In this study, we first focus our attention to the multicast that is known as a representative collective communication pattern observed in multiplexed networks. We proposed several time-efficient multicast schemes for various types of network topologies, and gave theoretical and empirical evaluations of the schemes. More concretely, we obtained the following results through the project :1.Proposal of time-efficient multicast schemes for Cayley graphs, where the receivers of the message is restricted to the neighbors of the source node.2.Theoretical analysis of the greedy multicast schemes.3.Proposal of load balancing mechanism4.Proposal of path reservation protocols in QoS guaranteed routing schemes.

在本研究中，我们首先将注意力集中在多播上，多播被称为在多路复用网络中观察到的代表性集体通信模式。我们针对各种类型的网络拓扑提出了几种高效的组播方案，并对这些方案进行了理论和实证评估。更具体地说，我们通过该项目获得了以下成果：1.针对凯莱图提出了时间高效的组播方案，其中消息的接收者仅限于源节点的邻居。2.贪婪组播方案的理论分析.3.负载均衡机制的建议4.QoS保证路由方案中路径预留协议的建议。

项目成果

S.Fujita: "A Semi-Dynamic Multiprocessor Scheduling Algorithm with an Asymptotically Optimal Performance Ratio"Lecture Notes on Computer Science. 2400. 240-247 (2002)

S.Fujita：“具有渐进最优性能比的半动态多处理器调度算法”计算机科学讲义。

S.Fujita: "On-Line Grid Packing with a Single Active Grid"Information Processing Letters. 85-4,28. 199-204 (2003)

S.Fujita：“使用单个活动网格进行在线网格打包”信息处理信件。

S.Fujita: "Distributed Location of Shared Resources and its Application to the Load Sharing Problem in Heterogeneous Distributed Systems"Lecture Notes in Computer Science. 2858. 393-401 (2003)

S.Fujita：“共享资源的分布式位置及其在异构分布式系统中的负载共享问题中的应用”计算机科学讲义。

S.Fujita: "A Greedy Multicast Algorithm in k-ary n-cubes and its Worst Case Analysis"IEICE Trans. Inf. & Syst.. E86-D. 238-245 (2003)

S.Fujita：“k 进制 n 立方体中的贪婪多播算法及其最坏情况分析”IEICE Trans。

M.Mito: "On Heuristics for Solving Winner Determination Problem in Combinatorial Auctions"Proc. IAT 2003. 25-31 (2003)

M.Mito：“关于解决组合拍卖中获胜者确定问题的启发式方法”Proc。