Universal bounds on buffer size for packetizing fluid policies in input queued, crossbar sw.pdf
- 1、本文档共9页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
Universal bounds on buffer size for packetizing fluid policies in input queued, crossbar sw
Universal Bounds on Buffer Size for Packetizing
Fluid Policies in Input Queued, Crossbar Switches
Michael Rosenblum1
Department of Mathematics
Massachusetts Institute of Technology
Email: mrosen@math.mit.edu
Michel X. Goemans?
Department of Mathematics
Massachusetts Institute of Technology
Email: goemans@math.mit.edu
Vahid Tarokh?
Division of Engineering
and Applied Sciences
Harvard University
Email: vahid@deas.harvard.edu
Abstract— In this paper, we consider a type of on-line, traffic
scheduling problem in input queued, crossbar switches. The
input to a problem, at each time step, is a set of desired traffic
rates. These traffic rates in general cannot be exactly achieved
since they assume arbitrarily small fractions of packets can be
transmitted at each time step. The goal of the traffic scheduling
problem is to closely approximate the given sequence of traffic
rates by a sequence of switch uses in which only whole packets
are sent. The focus of this paper is bounding the costs incurred
in using such an approximation, in terms of the additional buffer
size required.
We establish universal bounds on the additional buffer size
due to sending only whole packets; these bounds do not depend
on the particular distribution of the input traffic, require no
speedup, and guarantee 100% throughput. Specifically, for an
N × N input queued, crossbar switch, an on-line, packetizing
algorithm is presented that guarantees 100% throughput with a
buffer requirement of (N +1)2/4 packets per input port with no
speedup. The algorithm can be improved to run in O(N log N)
time, using a fast algorithm for edge-coloring bipartite multi-
graphs. In the reverse direction, it is shown for an N ×N input
queued, crossbar switch, that any on-line, packetizing algorithm
with no speedup requires a buffer size of N/e ? 2 packets per
input port. We also extend the main packetizing algorithm in
this paper to a general class of switch architectures.
Keywords: Deterministic network calculus, Graph the
您可能关注的文档
- The Effects of Electronic Supply Chain Design (eSCD) on Coordination and Knowledge Sharing.pdf
- The Effects of Technological Advancement.pdf
- The Emergence of Self-organizing E-commerce Ecosystems in Remote Villages of China.pdf
- The entanglement in one-dimensional random XY spin chain with Dzyaloshinskii-Moriya interac.pdf
- The Ethics of Belief.pdf
- The ESANASA SOHO Mission Interruption Using the STAMP Accident Analysis Technique for a Sof.pdf
- The FABP4 gene polymorphism is associated with meat.pdf
- The Features of English News Headline.ppt
- The fatigue crack initiation at the interface between matrix and δ-ferrite in 304L stainless steel.pdf
- The Gamma-Ray Blazar Content of the Northern Sky.pdf
文档评论(0)