三层Clos网络不阻塞问题研究.pdf

摘要且对连续带宽也是正确的。本文证明了当芫痪保珻和对多开关网络问题是一个起源于电话网络连接的组合优化问题。起初,人们研究的是经典的线路转接模型下的开关网络。但是,随着数字和信息技术的不断发展,又产生了许多新的模型,比如:多速模型、多点传送模型以及多速多点传送模型。开关网络越来越受到人们的广泛关注,在许多领域发挥了重要的作用,比如说数据传输、电话会议、广播、卫星传送等等。在开关网络的诸多经典网络中,三层网络被认为是最基本、最常用的多层互联网。本文主要研究和分析三层网络在这些新的模型下的不阻塞性质:严格不阻塞、广义不阻塞和可重排不阻塞。全文共分为五章。第一章主要介绍与开关网络有关的一些基本概念和预备知识。由于我们在研究三层网络的可重排不阻塞性质时用到了图论中的着色理论,所以第二章的第一节主要介绍了图论的一些基本概念和基础知识,第二节则介绍了着色理论。但是,利用图论中的知识和方法来研究开关网络的问题时,我们不得不面俚囊桓鑫侍饩褪峭嫉拇娲⑽侍狻R虼耍谌谥饕=樯芎第三章主要研究三层网络在多速环境下的不阻塞性质。本章第一节详细介绍了多速模型,第二节则主要介绍三层网络在多速模型下的一些己知结果。本章第三节主要研究在只有两种速度蚥的情况下三层网络的广义不阻塞性质。由于以前人们对两速网络的研究并不包括的情形。本文针对的情形,我们给出了最好的预留方案来完成对一般的两速情形的讨论。第四节主要研究三层网络在多速环境下的可重排不阻塞性质。和给出了一个猜想:若每个请求的权重取自一个给定的具有鲋亓康募希蛉鉉鏲,瑀强芍嘏挪蛔枞牡鼻仅当。更进一步,这个猜想看起来不仅对离散带宽是正确的,而速网络的可重排性的猜想在离散带宽情形和连续带宽情形下都是正确的。第四章主要研究三层网络在多点传送环境下的广义不阻塞性质。本章第一节详细介绍了多点传送模型,第二节则主要介绍三层网络在多点传送模型下的一些已知结果。和证明了,如果/,则三层网络礼,瑀嵌嗟愦凸阋宀蛔枞模饫飠是图理论,并给出了我们得到的结果。/瑀
赋值未必在娜≈捣段琺一瑀里。在本章第三节中我们将证明如果/,则三层网络琺,是多点传送广义不阻塞的,其中钦N颐堑慕峁趴砹硕詚的限制,从而比和的结果要好。同时,由于挥辛巳≈捣段У南拗疲而和给出的以蛂的函数为表达式的慕缦奘钦返摹>进一步的分析,我们可以改进他们的这个界限。第五章主要研究三层网络在多速多点传送环境下的不阻塞性质。本章第一节详细介绍了多速多点传送模型,第二节则主要介绍三层网络在多速多点传送模型下的。些已知结果。由于这是最复杂的一种模型,分析起来极为困难,因此,到至今为止所得结论仍很少。本章第三节研究三层网络在两种最简单的多速多点传送模型,即一速多点传送和两速多点传送模型下的广义不阻塞性质。虳隽艘桓鲈谙拗频睦肷⒋硖跫碌墓赜诙嗨俣嗟传送可重排不阻塞网络的结果。在第四节中我们将说明他们的这个结果在计数上的一点错误,并加以纠正,而且得到结果改进了虳摹关键词:开关网络,三层网络,严格不阻塞,广义不阻塞,可重排不阻塞,着色,和图,和数。正整数。通过给桓龈持担怯缮鲜鼋崧鄣玫搅艘桓鲆裕和暮数为表达式的慕缦蕖5牵飧鼋缦藁勾嬖谝恍┤毕荩核嵌詚的摘要一Ⅱ一
甌甋琺,.一瓾瑂琺琩琤,.,/.瑃甋琲猻,猻..
舢。笛‘鲦啊X峤甿骸芮鋗¨∽一絩痾瑆胁芫话【琺—,琺,/,琒一Ⅳ一:甕’..,,.,’阳
—琑珻琒琒一
第一章绪论组合优化问题与算法近几十年来,组合优化和图论得到了迅猛地发展,在运筹学、计算机科学、管理科学和应用数学等诸多学科都发挥了重要的作用。它们在社会生产和生活中有着广泛的应用,已经渗入到人们生活的方方面面。图论中存在着很多的组合优化问题,同时图论中的一些理论和方法又为解决组合优化问题提供了一种很好的方法和思路,它们是相辅相成的。本文所研究的开关网络问题也是一种组合优化问题。随着数字和信息技术的不断发展,开关网络越来越深入到人们生活的中心,在许多领域发挥了重要的作用,比如说通讯、数据传输、电话会议、广播、卫星传送等等。本章将对本文所涉及的组合优化和开关网络的一些基本知识和研究成果作逐一介绍。至于图论中的一些基础知识和研究成果我们将在下一章中介绍。组合优化问题又称离散优化问题,是一类重要的优化问题。尽管某些组合优化问题有着悠久的历史渊源,被费马、欧拉戎诙嘀的数学家研究过,但作为运筹学的一个独立分支而发展壮大起来还是近儿十年的事。随着计算机科学、管理科学和现代化生产技术等的日益发展,这类问题与日俱增,越来越受到运筹学、应用数学、计算机科学及管理科学等诸多学科的高度重视。随着人们对组合优化问题的研究的不断深入,现在这类问题和研究方法已在网络通信、物流管理等诸多领域发挥了重要作用,对人们的生产、生活产生了重要的影响