基于存储的电路交换网络路由与资源调度算法研究

摘要

目前，互联网(Internet)的高速发展带来了用户数量与应用种类的指数型增长，不断增长的数据流量与有限的网络带宽资源之间的矛盾正变得日趋突出。因此，如何充分利用网络资源进行海量数据传输，有着重要的现实意义。
　　电路交换网络，因其有着大带宽、低延迟、可保证的服务质量(Quality of Service，QoS)等优点，在现在的传输网中有着广泛的部署与应用来承载数据传输的任务。然而，电路交换“端到端建路机制”会带来网络带宽资源浪费问题。传统电路交换建路时，要求所建电路上的每一条链路都提供相同大小的带宽。可是在实际网络环境中，用户需求的多样性（请求带宽大小不同，请求源地址与目的地址不同，请求持续时间不同），会导致网络带宽资源的不均衡性。因此，电路交换网络“苛刻”的建路条件使得所建电路的最大可用带宽被该电路上拥有最小可用带宽的链路所限制。而当出现部分链路存在可用带宽资源而部分链路没有可用带宽时，端到端的电路便无法建立，这就造成了存在剩余带宽资源而不能利用的资源浪费情况。因此我们知道，解决电路交换“端到端建路机制”带来的带宽资源浪费问题，能从根本上提高整个网络的带宽资源利用率。
　　为了充分利用网络带宽资源，我们提出基于存储的电路交换网络的路由和资源调度问题(Routing and Resource Allocation，RRA)，打破传统电路交换的建路限制，通过给交换节点装备存储设备缓存数据，允许建立不均匀速率的端到端电路。我们证明了RRA是NP-Complete问题，提出了启发式算法Store Wait Forward(SWF)来应对RRA问题，并分别针对静态业务和动态业务对RRA问题进行了研究和仿真。仿真结果表明，存储的引入能够显著的减少请求的总的传输时间，提高链路利用率。而且在动态业务模型下，基于存储的方法能够降低网络的阻塞率。当然，存储的引入也带来了比传统电路交换更大的等待延时。考虑到大量的数据传输业务是时延不敏感的，我们认为基于存储的电路交换能够很好的应对这类时延不敏感的应用，而且SWF也是一个有效的算法。

目录

第一章 绪论

1.1 研究背景

1.2 电路交换技术概述

1.3 基于存储的电路交换

1.4 论文内容安排

第二章 国内外研究现状

2.1 引言

2.2 路由与资源调度算法层面

2.3 传输协议层面

2.4 网络架构层面

2.5 本章小结

第三章 静态RRA问题研究

3.1 静态RRA问题描述

3.2 静态RRA问题的NP-Complete证明

3.3 时变图

3.4 LP问题整理

3.5 Store Wait Forward算法

3.6 仿真结果与分析

3.7 本章小结

第四章 动态RRA问题研究

4.1 动态RRA问题描述

4.2 研究方法

4.3 仿真结果与分析

4.4 本章小结

第五章 总结与展望

5.1 研究工作总结

5.2 今后工作展望

参考文献

致谢

攻读学位期间发表的学术论文

攻读学位期间参与的项目