Heterogeneous packet processing in shared memory buffers

详细信息    查看全文

• 作者：Patrick Eugster^a ; ^b ; ^{peugster@cs.purdue.edu" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Kirill Kogan^c ; ^{kirill.kogan@imdea.org" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Sergey I. Nikolenko^d ; ^e ; ^{sergey@logic.pdmi.ras.ru" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Alexander V. Sirotkin^f ; ^{avsirotkin@hse.ru" class="auth_mail" title="E-mail the corresponding author}Author Vitae
• 关键词：Buffer management ; Admission control ; Competitive analysis
• 刊名：Journal of Parallel and Distributed Computing
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：99
• 期：Complete
• 页码：1-13
• 全文大小：1237 K

文摘

Packet processing increasingly involves heterogeneous requirements. We consider the well-known model of a shared memory switch with bounded-size buffer and generalize it in two directions. First, we consider unit-sized packets labeled with an output port and a processing requirement (i.e., packets with heterogeneous processing), maximizing the number of transmitted packets. We analyze the performance of buffer management policies under various characteristics via competitive analysis that provides uniform guarantees across traffic patterns (Borodin and ElYaniv 1998). We propose the Longest-Work-Drop policy and show that it is at most class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0743731516300879&_mathId=si47.gif&_user=111111111&_pii=S0743731516300879&_rdoc=1&_issn=07437315&md5=15841442e7bb625585f011c59f38415f" title="Click to view the MathML source">2class="mathContainer hidden">class="mathCode">$2$-competitive and at least class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0743731516300879&_mathId=si35.gif&_user=111111111&_pii=S0743731516300879&_rdoc=1&_issn=07437315&md5=2893695b8b6745a5fd8fdf60871edf7e">class="imgLazyJSB inlineImage" height="17" width="25" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0743731516300879-si35.gif">class="mathContainer hidden">class="mathCode">$\sqrt{2}$-competitive. Second, we consider another generalization, posed as an open problem in Goldwasser (2010), where each unit-sized packet is labeled with an output port and intrinsic value, and the goal is to maximize the total value of transmitted packets. We show first results in this direction and define a scheduling policy that, as we conjecture, may achieve constant competitive ratio. We also present a comprehensive simulation study that validates our results.