跳到主要內容

臺灣博碩士論文加值系統

(3.239.4.127) 您好!臺灣時間:2022/08/20 07:08
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:虞繼堯
研究生(外文):Chi-Yao Yue
論文名稱:負載平衡之布可夫范紐曼交換機之頻寬保證
論文名稱(外文):Providing Guaranteed Rate Services in Load Balanced Birkhoff-von Neumann Switches
指導教授:張正尚
指導教授(外文):Cheng-Shang Chang
學位類別:碩士
校院名稱:國立清華大學
系所名稱:通訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:38
中文關鍵詞:負載平衡布可夫范紐曼交換機頻寬保證截止期限最早優先時間框架有限延遲
外文關鍵詞:load balancedBirkhoff-von Neumann Switchesguaranteed rate servicesearliest deadline firsttime framedelay bound
相關次數:
  • 被引用被引用:0
  • 點閱點閱:177
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本篇論文提出了兩種策略,使得在負載平衡布可夫范紐曼交換機上可對封包流達成頻寬保證服務。此兩種策略為:以EDF(截止期限最早者優先)為基礎的策略與以frame(時間框架)為基礎的策略。
在以EDF為基礎的策略當中,我們使用具有多級暫存器的負載平衡布可夫范紐曼交換機架構,並對於每個頻寬保證封包流的封包設定一目標送達時間,此目標送達時間為將此封包送入一輸出能力為其保證頻寬的盡力輸出連結後的送達時間。在中央暫存器之前我們加上了一等量延遲控制機制,根據每個封包的目標送達時間與第一級最大延遲決定其輸出的時間。另外,在重組與輸出暫存器當中我們採取EDF的封包排程策略。結果我們得到每個封包的起始至終端延遲將不大於其目標送達時間與一常數之和,此常數將只與封包流數目和交換機大小有關。
在以frame為基礎的策略當中,我們將一些時槽組合成一固定大小的時間框架。利用到達交換機的封包的到達時間與其所屬的封包流,其將被置於暫存器中正確的位置。假如到達封包流的流量符合一些限制,則每個封包的起始至終端延遲與中央暫存器的大小都將不大於一常數,此常數將只與時間框架大小與交換機大小有關。在許多方面,此種策略將比以EDF為基礎的策略簡單,如:(i) 線上計算複雜度為O(1),(ii) 有限的中央暫存器使得其可以被實現在單一晶片中,(iii) 縱橫式交換機的連結變換速度降低,(iv) 不需要重組與輸出暫存器,(v) 可變長度封包將可以被傳送並且不必經過切割與重組的程序。

In this thesis, we propose two schemes for the load balanced
Birkhoff-von Neumann switches to provide guaranteed rate services. As in [7], the first scheme is based on an Earliest
Deadline First (EDF) scheduling policy. In such a scheme, we
assign every packet of a guaranteed rate flow a targeted
departure time that is the departure time from the corresponding
work conserving link with capacity equal to the guaranteed rate.
By adding a jitter control mechanism in front of the buffer at the second stage and running the EDF policy at the output buffer, we show that the end-to-end delay for every packet of a guaranteed rate flow is bounded by the sum of its targeted departure time and a constant that only depends on the number of flows and the size of the switch.
Our second scheme is a frame based scheme as in Keslassy and
McKeown [17]. There, time slots are grouped into fix size frames. Packets are placed in appropriate bins (buffers) according to their arrival times and their flows. We show that if the incoming traffic satisfies certain assumptions, then the end-to-end delay for every packet and the size of the central buffers are both bounded by constants that only depend on the size of the switches and the frame size. The second scheme is much simpler than the first one in many aspects:
(i) the on-line complexity is $O(1)$ as there is no need
for EDF, (ii) central buffers are finite and thus
can be built into a single chip, (iii) connection patterns of the two switch fabrics are changed less frequently, (iv) there is no need for resequencing-and-output buffer after the
second stage, and (v) variable length packets may be handled without segmentation and reassembly.

摘要 ……………………………………………………………… i
致謝 ……………………………………………………………… ii
目錄 ……………………………………………………………… iii
第一章 簡介 ………………………………………………… 1
第二章 以EDF為基礎提供頻寬保證的策略 ………………… 2
第三章 以frame為基礎提供頻寬保證的策略 ……………… 3
第四章 結論 ………………………………………………… 4
附錄 英文稿 ………………………………………………… 5

[1] M. Ajmone Marsan, A. Bianco, P. Giaccone, E. Leonardi
and F. Neri, ``On the throughput of input-queued cell-based switches
with multicast traffic,'' Proc. IEEE INFOCOM'01, pp. 1664-1672, 2001.
[2] T. Anderson, S. Owicki, J. Saxes and C. Thacker,
``High speed switch scheduling for local area networks,''
ACM Trans. on Computer Systems, Vol. 11, pp. 319-352, 1993.
[3] G. Birkhoff, ``Tres observaciones sobre el algebra lineal,''
Univ. Nac. Tucuman Rev. Ser. A, Vol. 5, pp. 147-151, 1946.
[4] C.S. Chang. Performance Guarantees in Communication Networks. London: Springer-Verlag, 2000.
[5] C.S. Chang, W.J. Chen and H.Y. Huang,
``On service guarantees for input buffered crossbar switches:
a capacity decomposition approach by Birkhoff
and von Neumann,'' IEEE IWQoS'99, pp. 79-86, London, U.K., 1999.
[6] C.S. Chang, W.J. Chen and H.Y. Huang,
``Birkhoff-von Neumann input buffered crossbar switches,''
IEEE INFOCOM2000, pp. 1614-1623, Tel Aviv, Israel, 2000.
[7] C.S Chang, D.S. Lee and Y.S. Jou, ``Load
balanced Birkhoff-von Neumann switches, part I: one-stage
buffering,'' em Computer Communications, Vol. 25, pp. 611-622, 2002.
[8] C.S. Chang, D.S. Lee and C.M. Lien,
``Load balanced Birkhoff-von Neumann switch, part II: Multi-stage
buffering,'' Computer Communications, Vol. 25, pp. 623-634, 2002.
[9] S.-T. Chuang, A. Goel, N. McKeown and B. Prabhkar,
``Matching output queueing with a combined input output queued
switch,'' IEEE INFOCOM'99, pp. 1169-1178, New York, 1999.
[10] R.L. Cruz, `` SCED+: efficient management of quality
of service guarantees,'' Proc. of IEEE INFOCOM'98.
[11] A. Demers, S. Keshav, and S. Shenkar, ``Analysis
and simulation of a fair queueing algorithm,''
in Proc. SIGCOMM'89, pp. 1-12, Austin, TX, Sept. 1989.
[12] P. Goyal and H.M. Vin, ``Generalized guaranteed rate scheduling algortihms: a framework,'' IEEE/ACM Transactions on Networking, Vol. 5, pp. 561-571, 1997.
[13] A. Hung, G. Kesidis and N. McKeown, ``ATM input-buffered
switches with guaranteed-rate property,'' Proc. IEEE ISCC'98,
Athens, pp. 331-335, 1998.
[14] S. Iyer, A. Awadallah and N. McKeown, ``Analysis of a packet switch with memories running at slower than line speed'',
Proceedings of IEEE INFOCOM 2000}.
[15] S. Iyer and N. McKeown, ``Making parallel packet switch
practical,'' Proc. IEEE INFOCOM 2001, Anchorage, Alaska,
U.S.A.
[16] M. J. Karol, M. G. Hluchyj, and S. P. Morgan, ``Input
Versus Output Queueing on a Space-Division Packet Switch,''
IEEE Trans. Commun., Vol. COM35, NO.12, Dec. 1987.
[17] I. Keslassy and N. McKeown,
``Maintaining packet order in two-stage switches,''
Proc. of IEEE INFOCOM, New York, 2002.
[18] T.T. Lee and C.H. Lam, ``Path switching-a quasi-static routing
scheme for large scale ATM packet switches,''
IEEE Journal on Selected Areas of Communications,
Vol. 15, pp. 914-924, 1997.
[19] S. Li and N. Ansari, ``Input-queued switching with
QoS guarantees,'' IEEE INFOCOM'99, pp. 1152-1159, New York,
1999.
[20] Y. Li, S. Panwar and H.J. Chao, ``On the performance of
a dual round-robin switch,'' Proc. IEEE INFOCOM'01, pp. 1688-1697, 2001.
[21] N. McKeown, ``Scheduling algorithms for input-queued cell
switches,'' PhD Thesis. University of California at Berkeley, 1995.
[22] N. McKeown, V. Anantharam and J. Walrand,
``Achieving 100% throughput in an input-queued switch,''
Proc. IEEE INFOCOM'96, pp. 296-302, 1996.
[23] A. Mekkittikul and N. McKeown, ``A practical
scheduling algorithm to achieve 100% throughput in input-queued
switches,'' Proc. IEEE INFOCOM'98.
[24] A.K. Parekh and R.G. Gallager, ``A generalized
processor sharing approach to flow control in integrated service
networks: the single-node case,'' IEEE/ACM Transactions on Networking, Vol. 1, pp. 344-357, 1993.
[25] D. Stiliadis and A. Varma, ``Providing bandwidth guarantees
in an input-buffered crossbar switch,'' Proc. IEEE INFOCOM'95},
pp. 960-968, 1995.
[26] I. Stoica and H. Zhang, ``Exact emulation of an
output queueing switch by a combined input output queueing switch,'' IEEE IWQoS'98, pp. 218-224, Napa, California, 1998.
[27] J. von Neumann, ``A certain zero-sum two-person game
equivalent to the optimal assignment problem, '' Contributions
to the Theory of Games, Vol. 2, pp. 5-12, Princeton University
Press, Princeton, New Jersey, 1953.
[28] L. Zhang, ``Virtualclock: a new traffic
control algorithm for packet switching networks,''
ACM Transactions on Computer Systems, Vol. 9, pp. 101-124, 1991.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top