Concave switching in single-hop and multihop networks
Concave switching in single-hop and multihop networks
复制标题
单跳和多跳网络中的凹交换
DOI：
10.1007/s11134-015-9447-9
复制
发表时间：
2015
期刊：
影响因子：
1.2
通讯作者：
N. Walton
中科院分区：
文献类型：
--
作者：
N. Walton
交换交换网络模拟了无线网络、输入排队交换机和许多其他网络通信系统。我们考虑（$$\alpha，g$$α，g）-切换策略;这些策略提供了Tassiulas和Ephremides（IEEE Trans Autom Control 37（12）：4936-1948，1992）的最大权重策略和具有Mo和Walrand分配的加权$$\alpha $$α-公平（IEEE/ACM Trans Netw 8（5）：556-567，2000）的一般化，其通常应用于带宽共享网络（Massoulié和Roberts in IEEE/ACM Trans Netw 10（3）：320-328，2002）。对于单跳交换网络，我们证明了这类随机策略的最大稳定性。因此，这些策略具有与MaxWeight策略相同的一阶行为。然而，对于多跳网络，这些广义策略中的一些解决了MaxWeight/BackPressure策略的一些关键弱点。对于具有固定路由的多跳网络，我们考虑称为比例策略（或（1，log）-policy）的策略。在此设置中，BackPressure策略是最稳定的，但必须在每个节点为每个路由目的地维护一个队列，该队列通常会随着网络的大小快速增长。然而，比例路由器只需要为每个传出链路维护一个队列，该队列通常在数量上是有限的。与互联网路由一样，通过维护每个链路的路由，每个节点只需要知道每个数据包的下一跳，而不是整个路由。此外，与BackPressure相反，Proportional队列不比较下游队列长度以确定权重;仅需要本地链路信息。这导致了更大的潜力，分解实现的政策。通过减少参数和熵参数，我们证明，同时保持大幅减少的开销，比例缩放实现最大的吞吐量稳定性。
Switched queueing networks model wireless networks, input-queued switches, and numerous other networked communications systems. We consider an ($$\alpha ,g$$α,g)-switch policy; these policies provide a generalization of the MaxWeight policies of Tassiulas and Ephremides (IEEE Trans Autom Control 37(12):4936–1948, 1992) and the weighted $$\alpha $$α-fair with allocations of Mo and Walrand (IEEE/ACM Trans Netw 8(5):556–567, 2000) which are typically applied to Bandwidth Sharing Networks (Massoulié and Roberts in IEEE/ACM Trans Netw 10(3):320–328, 2002). For single-hop switch networks, we prove the maximum stability property for this class of randomized policies. Thus these policies have the same first-order behavior as the MaxWeight policies. However, for multihop networks some of these generalized polices address a number of critical weakness of the MaxWeight/BackPressure policies. For multihop networks with fixed routing, we consider a policy called the Proportional Scheduler (or (1, log)-policy). In this setting, the BackPressure policy is maximum stable, but must maintain a queue at each node for every route destination, which typically grows rapidly with a network’s size. However, the Proportional Scheduler only needs to maintain a queue for each outgoing link, which is typically bounded in number. As is common with Internet routing, by maintaining per-link queueing, each node only needs to know the next hop for each packet and not its entire route. Further, in contrast to BackPressure, the Proportional Scheduler does not compare downstream queue lengths to determine weights; only local link information is required. This leads to greater potential for decomposed implementations of the policy. Through a reduction argument and an entropy argument, we demonstrate that, while maintaining substantially less queueing overhead, the Proportional Scheduler achieves maximum throughput stability.