Loading…
Approximations to maximum weight matching scheduling algorithms of low complexity
The choice of the scheduling algorithm is a major design criterion of a switch. Whereas it is known that maximum weight matching algorithms guarantee the stability of an input-queued switch, their computational complexity does not allow their practical deployment. In consequence, researchers have de...
Saved in:
Main Author: | |
---|---|
Format: | Conference Proceeding |
Language: | English |
Subjects: | |
Online Access: | Request full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
cited_by | |
---|---|
cites | |
container_end_page | 305 |
container_issue | |
container_start_page | 300 |
container_title | |
container_volume | |
creator | Bauer, C. |
description | The choice of the scheduling algorithm is a major design criterion of a switch. Whereas it is known that maximum weight matching algorithms guarantee the stability of an input-queued switch, their computational complexity does not allow their practical deployment. In consequence, researchers have designed scheduling algorithms of low complexity and with satisfying performance features. We extend this field of research by investigating the application of matching algorithms of low complexity that approximate maximum weight matching algorithms as scheduling algorithms for input-queued switches. We prove that an algorithm that approximates a maximum weight matching algorithm with approximation parameters (c, d), stabilizes a combined input/output-queued switch with a speed-up of 1/c. As an application, we show that four known scheduling algorithms of low complexity stabilize a combined input/output-queued switch with a speed-up of two. Finally, we prove that the improve/spl I.bar/matching algorithm can stabilize an input-queued switch when it is deployed with a speed-up of (3/2)+/spl epsiv/. |
doi_str_mv | 10.1109/AICT.2005.29 |
format | conference_proceeding |
fullrecord | <record><control><sourceid>ieee_6IE</sourceid><recordid>TN_cdi_ieee_primary_1517646</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>1517646</ieee_id><sourcerecordid>1517646</sourcerecordid><originalsourceid>FETCH-LOGICAL-i213t-cdcfbf6fb37f9db7abac6fa7a434bb78eed3c31dae9ddc2af720767ee76a72ac3</originalsourceid><addsrcrecordid>eNotj8lqwzAARAWl0DbNrbde9AN2tdiSdTSmSyBQCuk5aLVV7MhYCkn-virpXGbeZeAB8IRRiTESL-2m25UEobok4gY8IM5ETWjTiDuwjvEH5VQ1rjG9B1_tPC_h7CeZfDhEmAKcZMbjBE_W90PKmPTgDz2MerDmOP5NOfZh8WmYIgwOjuEEdZjm0Z59ujyCWyfHaNf_vQLfb6-77qPYfr5vunZbeIJpKrTRTjnmFOVOGMWlkpo5yWVFK6V4Y62hmmIjrTBGE-k4yR7cWs4kJ1LTFXi-_npr7X5essJy2WcrzipGfwEuzVCG</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>Approximations to maximum weight matching scheduling algorithms of low complexity</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Bauer, C.</creator><creatorcontrib>Bauer, C.</creatorcontrib><description>The choice of the scheduling algorithm is a major design criterion of a switch. Whereas it is known that maximum weight matching algorithms guarantee the stability of an input-queued switch, their computational complexity does not allow their practical deployment. In consequence, researchers have designed scheduling algorithms of low complexity and with satisfying performance features. We extend this field of research by investigating the application of matching algorithms of low complexity that approximate maximum weight matching algorithms as scheduling algorithms for input-queued switches. We prove that an algorithm that approximates a maximum weight matching algorithm with approximation parameters (c, d), stabilizes a combined input/output-queued switch with a speed-up of 1/c. As an application, we show that four known scheduling algorithms of low complexity stabilize a combined input/output-queued switch with a speed-up of two. Finally, we prove that the improve/spl I.bar/matching algorithm can stabilize an input-queued switch when it is deployed with a speed-up of (3/2)+/spl epsiv/.</description><identifier>ISBN: 0769523889</identifier><identifier>ISBN: 9780769523880</identifier><identifier>DOI: 10.1109/AICT.2005.29</identifier><language>eng</language><publisher>IEEE</publisher><subject>Algorithm design and analysis ; Approximation algorithms ; Computational complexity ; Laboratories ; Packet switching ; Processor scheduling ; Scheduling algorithm ; Stability ; Switches ; Telecommunication switching</subject><ispartof>Advanced Industrial Conference on Telecommunications/Service Assurance with Partial and Intermittent Resources Conference/E-Learning on Telecommunications Workshop (AICT/SAPIR/ELETE'05), 2005, p.300-305</ispartof><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/1517646$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2056,4048,4049,27924,54919</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/1517646$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Bauer, C.</creatorcontrib><title>Approximations to maximum weight matching scheduling algorithms of low complexity</title><title>Advanced Industrial Conference on Telecommunications/Service Assurance with Partial and Intermittent Resources Conference/E-Learning on Telecommunications Workshop (AICT/SAPIR/ELETE'05)</title><addtitle>AICT</addtitle><description>The choice of the scheduling algorithm is a major design criterion of a switch. Whereas it is known that maximum weight matching algorithms guarantee the stability of an input-queued switch, their computational complexity does not allow their practical deployment. In consequence, researchers have designed scheduling algorithms of low complexity and with satisfying performance features. We extend this field of research by investigating the application of matching algorithms of low complexity that approximate maximum weight matching algorithms as scheduling algorithms for input-queued switches. We prove that an algorithm that approximates a maximum weight matching algorithm with approximation parameters (c, d), stabilizes a combined input/output-queued switch with a speed-up of 1/c. As an application, we show that four known scheduling algorithms of low complexity stabilize a combined input/output-queued switch with a speed-up of two. Finally, we prove that the improve/spl I.bar/matching algorithm can stabilize an input-queued switch when it is deployed with a speed-up of (3/2)+/spl epsiv/.</description><subject>Algorithm design and analysis</subject><subject>Approximation algorithms</subject><subject>Computational complexity</subject><subject>Laboratories</subject><subject>Packet switching</subject><subject>Processor scheduling</subject><subject>Scheduling algorithm</subject><subject>Stability</subject><subject>Switches</subject><subject>Telecommunication switching</subject><isbn>0769523889</isbn><isbn>9780769523880</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2005</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNotj8lqwzAARAWl0DbNrbde9AN2tdiSdTSmSyBQCuk5aLVV7MhYCkn-virpXGbeZeAB8IRRiTESL-2m25UEobok4gY8IM5ETWjTiDuwjvEH5VQ1rjG9B1_tPC_h7CeZfDhEmAKcZMbjBE_W90PKmPTgDz2MerDmOP5NOfZh8WmYIgwOjuEEdZjm0Z59ujyCWyfHaNf_vQLfb6-77qPYfr5vunZbeIJpKrTRTjnmFOVOGMWlkpo5yWVFK6V4Y62hmmIjrTBGE-k4yR7cWs4kJ1LTFXi-_npr7X5essJy2WcrzipGfwEuzVCG</recordid><startdate>2005</startdate><enddate>2005</enddate><creator>Bauer, C.</creator><general>IEEE</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope></search><sort><creationdate>2005</creationdate><title>Approximations to maximum weight matching scheduling algorithms of low complexity</title><author>Bauer, C.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i213t-cdcfbf6fb37f9db7abac6fa7a434bb78eed3c31dae9ddc2af720767ee76a72ac3</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2005</creationdate><topic>Algorithm design and analysis</topic><topic>Approximation algorithms</topic><topic>Computational complexity</topic><topic>Laboratories</topic><topic>Packet switching</topic><topic>Processor scheduling</topic><topic>Scheduling algorithm</topic><topic>Stability</topic><topic>Switches</topic><topic>Telecommunication switching</topic><toplevel>online_resources</toplevel><creatorcontrib>Bauer, C.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan All Online (POP All Online) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE</collection><collection>IEEE Proceedings Order Plans (POP All) 1998-Present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Bauer, C.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Approximations to maximum weight matching scheduling algorithms of low complexity</atitle><btitle>Advanced Industrial Conference on Telecommunications/Service Assurance with Partial and Intermittent Resources Conference/E-Learning on Telecommunications Workshop (AICT/SAPIR/ELETE'05)</btitle><stitle>AICT</stitle><date>2005</date><risdate>2005</risdate><spage>300</spage><epage>305</epage><pages>300-305</pages><isbn>0769523889</isbn><isbn>9780769523880</isbn><abstract>The choice of the scheduling algorithm is a major design criterion of a switch. Whereas it is known that maximum weight matching algorithms guarantee the stability of an input-queued switch, their computational complexity does not allow their practical deployment. In consequence, researchers have designed scheduling algorithms of low complexity and with satisfying performance features. We extend this field of research by investigating the application of matching algorithms of low complexity that approximate maximum weight matching algorithms as scheduling algorithms for input-queued switches. We prove that an algorithm that approximates a maximum weight matching algorithm with approximation parameters (c, d), stabilizes a combined input/output-queued switch with a speed-up of 1/c. As an application, we show that four known scheduling algorithms of low complexity stabilize a combined input/output-queued switch with a speed-up of two. Finally, we prove that the improve/spl I.bar/matching algorithm can stabilize an input-queued switch when it is deployed with a speed-up of (3/2)+/spl epsiv/.</abstract><pub>IEEE</pub><doi>10.1109/AICT.2005.29</doi><tpages>6</tpages><oa>free_for_read</oa></addata></record> |
fulltext | fulltext_linktorsrc |
identifier | ISBN: 0769523889 |
ispartof | Advanced Industrial Conference on Telecommunications/Service Assurance with Partial and Intermittent Resources Conference/E-Learning on Telecommunications Workshop (AICT/SAPIR/ELETE'05), 2005, p.300-305 |
issn | |
language | eng |
recordid | cdi_ieee_primary_1517646 |
source | IEEE Electronic Library (IEL) Conference Proceedings |
subjects | Algorithm design and analysis Approximation algorithms Computational complexity Laboratories Packet switching Processor scheduling Scheduling algorithm Stability Switches Telecommunication switching |
title | Approximations to maximum weight matching scheduling algorithms of low complexity |
url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-12T23%3A09%3A09IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Approximations%20to%20maximum%20weight%20matching%20scheduling%20algorithms%20of%20low%20complexity&rft.btitle=Advanced%20Industrial%20Conference%20on%20Telecommunications/Service%20Assurance%20with%20Partial%20and%20Intermittent%20Resources%20Conference/E-Learning%20on%20Telecommunications%20Workshop%20(AICT/SAPIR/ELETE'05)&rft.au=Bauer,%20C.&rft.date=2005&rft.spage=300&rft.epage=305&rft.pages=300-305&rft.isbn=0769523889&rft.isbn_list=9780769523880&rft_id=info:doi/10.1109/AICT.2005.29&rft_dat=%3Cieee_6IE%3E1517646%3C/ieee_6IE%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i213t-cdcfbf6fb37f9db7abac6fa7a434bb78eed3c31dae9ddc2af720767ee76a72ac3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=1517646&rfr_iscdi=true |