Control Techniques for Complex Networks

现在operations research那边关心的重点基本上就是heavy load情况下的性能分析和optimal control。主要原因在于traffic intensity没有达到网络的瓶颈容量的时候，情况相对简单，一般来说只要routing算法是stable的，网络就能平稳运行（虽然未必最优）。另外在heavry traffic的情况下，有可能利用大数定理或者中心极限定理简化模型，直接处理网络的fluid approximation或者diffusion approximation，而在这种情况下得到的算法如果满足某些条件，可以直接用到非heavy load的情况。

其实heavy load的假设有一个很大的问题。就派对论来说，如果只有一个队列，那么我
们知道\rho < 1是队列稳定的充分条件，不论arrival process和service time遵从什么
样的分布。可是如果是一个队列网络，只保证单个队列\rho < 1是否能保证系统稳定呢
？目前没有完整的证明，所以只能算作猜想。大多数人倾向于认可这个猜想，因为目前
为止所作的数值仿真没有能找到反例的。可是现在所有的网络控制都take it for gran
ted。这其实是一大隐患呢...

所有队列如果都满足\rho<1，而且网络的瓶颈只有一个的前提下，网络是可以平稳运行的（当然，这取决于routing policy）。当然，这里讨论的网络是比较简单的确定路由的网络，对于internet这样的随机路由的网络，似乎目前还没有结论。
这些东西在Sean Meyn的书里，还有他最近写的paper里面都有详细的讨论。

Sean Meyn的工作很大程度上更接近于manufactering networks，而不是communication networks。这也使得他更像一个做OR的，而不是干EE的。
现在在applied probability和OR的领域，在heavy traffic（\rho>=1）情况下的queueing system也是一个热点。但问题是即便是简单的排队系统，仍有太多的东西没有解决，所以就更不必说排队网络了。

Sean 的理论（h-MaxWeight policy）其实是可以用于随机网络模型（比如Controlled
Random Walk model）的。具体来说：Sean用workload方法来分析随机模型所对应的
averaged model （fluid model），得到workload vector或者relaxed workload
matrix；然后利用workload vector/matrix来构造h-function （a monotone convex
that vanishes only at the origin），最终得出的h-MaxWeight policy是用于随机模
型的。当所研究的随机模型满足一系列条件（比如network是经典Kelly type的，\rou \simeq 1 (heavy traffic condition)，single bottleneck等等）时，其所设计的
policy可以认为是approximately average-cost optimal的但是with logarithmic regret。
Multi bottleneck的复杂网络是Sean正在研究的问题，不过目前为止还没得到很好的结
果。
Sean的数学功底很深，他的这本书（CTCN）写的非常数学化，比较难懂。如果有兴趣的
话可以先从他的几篇paper看起，然后再来读他的书。
p.s.：
http://decision.csl.uiuc.edu/~meyn/pages/publistNetworks.html
1. Sequencing and Routing in Multiclass Queueing Networks. Part I: Feedback
Regulation. 2001
2. Sequencing and Routing in Multiclass Queueing Networks. Part II: Workload
Relaxations. 2003
3.Workload Models for Stochastic Networks: Value Functions and Performance
Evaluation. 2005
4.Stability and Asymptotic Optimality of Generalized MaxWeight Policies.
2007

这个问题似乎和这个版面的内容不太相符，不过也大致说说吧
综述文章
R. Albert, A.-L. Barabasi, "Statistical mechanics of complex network,"
Review of Modern Physics, vol. 74, no. 1, pp. 47-97, 2002.
X. F. Wang, "Complex networks: Topology, dynamics and synchronization,"
International Journal of Bifurcation and Chaos, vol. 12, no. 5, pp. 885-916,
2002.
M. E. J. Newman, "The structure and function of complex networks," SIAM
Reviews, vol. 45, no. 2, pp. 167-256, 2003.
X. F. Wang, G. Chen, "Complex networks: Small-world, scale-free and beyond,"
IEEE Circuits and Systems Magzine, vol. 3, no. 1, pp. 6-20, 2003.
L. A. N. Amarala. J. M. Ottino, "Complex networks: Augmenting the framework
for the study of complex systems," European Physical Journal B, vol. 38,
no. 2, pp. 147-162, 2004.
S. Boccalettia, V. Latorab, Y. Morenod, M. Chavezf, D.-U. Hwanga,
"Complex networks: Structure and dynamics," Physics Reports, vol. 424,
no. 4-5, pp. 175-308, 2006.
J. Fang, X. Wang, Z. Zhen, Q. Bi, Z. Di, X. Li, "New interdisciplinary
science: Network Science, Part I," Progress in Physics, vol. 27, no. 3,
pp. 239-343, 2007.
J. Fang, X. Wang, Z. Zhen, Q. Bi, Z. Di, X. Li, "New interdisciplinary
science: Network Science, Part II," Progress in Physics, vol. 27, no. 4,
pp. 361-448, 2007.
L. da F. Costa, F. A. Rodrigues, G. Travieso, P. R. Villas Boas,
"Characterization of complex networks: A survey of measurements,"
Advances in Physics, vol. 56, no. 1, pp. 167-242, 2007.
K. Boner, S. Sanyal, A. Vespignani, "Network Science," Chapter 12 of
Annual Review of Information Science & Technology, vol. 41, pp. 537-607,
2007.
书（Random Graph的书很多，未列出）
D. J. Watts, Small Worlds: The Dynamics of Networks between Order and
Randomness, Princeton University Press, Princeton, NJ, USA, 1999.
M. Newman, A.-L. Barabasi, D. J. Watts, The Structure and Dynamics of
Networks, Princeton University Press, Princeton, NJ, USA, 2006.

首先多数现实的排队系统都有overloaded的时候，研究overloaded的排队系统的特性当然也有价值。比方说这个队列的长度将以怎样的速率增加，是否有近似的方程可以表述等等。
一个比较现实一些的应用就是call center。一般来说话务中心的主要支出来源于人员开支，所以如果能保证一定的服务质量，当然是雇的话务员越少越好。而且现代的话务中心可能有几百上千个话务员同时工作。根据中心极限定理和大数定理，在这样的情况下，即便是\rho=1的情况下，用户的等待时间也不会很长。考虑到某些用户还会等不及就跑掉（就是你说的drop），所以在很多情况下连\rho=1都没有必要保证，\rho比1稍微大一点都没有问题。
所以一个现代的话务中心（通常建模成一个G/G/n+G队列），除非要求非常严格，否则是没有必要运行在\rho<1的情况下的。
这是一个很典型的OR的问题。这方面的工作主要是Ward Whitt等人在做。

我觉得你对bottleneck和heavy traffic的解释非常清楚易懂。我目前也是这么理解
heavy traffic的定义的。有很多文献谈过heavy traffic的定义和相关应用，就我个人
应用而言，比如这两篇文献就很好：
1. A. L. Stolyar. Maxweight scheduling in a generalized switch: state space
collapse and workload minimization in heavy traffic. 2004
2. S. L. Bell and R. J. Williams. Dynamic scheduling of a system with two
parallel servers in heavy traffic with complete resource pooling: Asymptotic
optimality of a continuous review threshold policy. 2001