Towards Real-Time Non-Preemptive Multicast Scheduling in Reconfigurable Data Center Networks

Towards Real-Time Non-Preemptive Multicast Scheduling in Reconfigurable Data Center Networks | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Towards Real-Time Non-Preemptive Multicast Scheduling in Reconfigurable Data Center Networks Fanlong Zhang, Jianglong Liu, Yuhang Wu, Quan Chen, Yuan Chai, and 1 more This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-3825114/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 12 Sep, 2024 Read the published version in Peer-to-Peer Networking and Applications → Version 1 posted 8 You are reading this latest preprint version Abstract Multicast has emerged as a primary communication pattern in datacenter networks due to the increasing demand for distributed data-parallel applications. To accelerate multicast traffic, the emerging reconfigurable circuit technology, which can establish circuit connections among switches, has been proposed as a promising paradigm for datacenter networks. This paper investigates how to accelerate the non-preemptive multicast flows in a demand-aware manner in reconfigurable datacenter networks. Firstly, we introduce the problem of scheduling circuit switches to minimize the average completion time and prove it to be NP-hard. To address the conflicts between different multicast flows under the bandwidth constraint, we consider the concept of splitting multicast flows and propose a two round matching algorithm. Additionally, to further reduce the average completion time, we introduce a method to utilize the remaining capacity of the ToR switches by splitting the unscheduled flows. The proposed algorithm is proved to have an approximation ratio of $2\sqrt{2n}$, where $n$ represents the number of Top-of-Rack (ToR) switches. Finally, the extensive simulations demonstrate the effectiveness of the proposed algorithm in reducing the average completion time of flows compared to state-of-the-art algorithms. Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 12 Sep, 2024 Read the published version in Peer-to-Peer Networking and Applications → Version 1 posted Editorial decision: Revision requested 26 Jun, 2024 Reviews received at journal 29 Jan, 2024 Reviewers agreed at journal 22 Jan, 2024 Reviewers agreed at journal 22 Jan, 2024 Reviewers invited by journal 21 Jan, 2024 Editor assigned by journal 17 Jan, 2024 Submission checks completed at journal 05 Jan, 2024 First submitted to journal 30 Dec, 2023 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-3825114","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":265391004,"identity":"5cc28db1-7ccf-4feb-90a8-423536068f54","order_by":0,"name":"Fanlong Zhang","email":"","orcid":"","institution":"Guangdong University of Technology","correspondingAuthor":false,"prefix":"","firstName":"Fanlong","middleName":"","lastName":"Zhang","suffix":""},{"id":265391005,"identity":"0bf0ee8a-468d-4813-be64-136e457dbf3f","order_by":1,"name":"Jianglong Liu","email":"","orcid":"","institution":"Guangdong University of Technology","correspondingAuthor":false,"prefix":"","firstName":"Jianglong","middleName":"","lastName":"Liu","suffix":""},{"id":265391006,"identity":"0f523eff-6e23-4d3d-859f-84642a42f1be","order_by":2,"name":"Yuhang Wu","email":"","orcid":"","institution":"Guangdong University of Technology","correspondingAuthor":false,"prefix":"","firstName":"Yuhang","middleName":"","lastName":"Wu","suffix":""},{"id":265391007,"identity":"7a6589ca-e26a-4317-bc48-acde5b30b6e2","order_by":3,"name":"Quan Chen","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAyElEQVRIiWNgGAWjYPACGwaGAyCajXgtaUAtzKRpOUyCFr4byc8eMNSct+u7kX+A4UPZYQb+2Q34tUjeSDM3YDh2O3nmjWQGxhnnDjNI3DmAX4vBjQQzCcaG28kGQC3MvG2HGQwkEghpSf8G1HIOouUvcVpyQLYcsANrYSRGi+SZN2USCceSEyTPPDY42HMunUfiBgEtfMfTt0l8qLGz5zue+PDBjzJrOf4ZBLSAIx2oJrEByuYhoB6qDAjsCascBaNgFIyCEQsAIY1FYUeRVHQAAAAASUVORK5CYII=","orcid":"","institution":"Guangdong University of Technology","correspondingAuthor":true,"prefix":"","firstName":"Quan","middleName":"","lastName":"Chen","suffix":""},{"id":265391008,"identity":"6177a24e-1000-46fc-a8bf-356e96038b0b","order_by":4,"name":"Yuan Chai","email":"","orcid":"","institution":"Guangdong University of Technology","correspondingAuthor":false,"prefix":"","firstName":"Yuan","middleName":"","lastName":"Chai","suffix":""},{"id":265391009,"identity":"b7e22677-faf3-4860-9533-1b5cf23791c8","order_by":5,"name":"Zhuowei Wang","email":"","orcid":"","institution":"Guangdong University of Technology","correspondingAuthor":false,"prefix":"","firstName":"Zhuowei","middleName":"","lastName":"Wang","suffix":""}],"badges":[],"createdAt":"2023-12-31 03:59:11","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-3825114/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-3825114/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s12083-024-01804-w","type":"published","date":"2024-09-12T15:58:19+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":64619287,"identity":"65c52ef5-bd7e-4c45-a340-e212dea22963","added_by":"auto","created_at":"2024-09-16 16:13:46","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":3296552,"visible":true,"origin":"","legend":"","description":"","filename":"NonPreemptiveMulticastScheduling.pdf","url":"https://assets-eu.researchsquare.com/files/rs-3825114/v1_covered_d9e55401-ee5a-4e47-baba-c95dfc5f130f.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Towards Real-Time Non-Preemptive Multicast Scheduling in Reconfigurable Data Center Networks","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"peer-to-peer-networking-and-applications","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"ppna","sideBox":"Learn more about [Peer-to-Peer Networking and Applications](http://link.springer.com/journal/12083)","snPcode":"12083","submissionUrl":"https://submission.nature.com/new-submission/12083/3","title":"Peer-to-Peer Networking and Applications","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"","lastPublishedDoi":"10.21203/rs.3.rs-3825114/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-3825114/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Multicast has emerged as a primary communication pattern in datacenter networks due to the increasing demand for distributed data-parallel applications. To accelerate multicast traffic, the emerging reconfigurable circuit technology, which can establish circuit connections among switches, has been proposed as a promising paradigm for datacenter networks. This paper investigates how to accelerate the non-preemptive multicast flows in a demand-aware manner in reconfigurable datacenter networks. Firstly, we introduce the problem of scheduling circuit switches to minimize the average completion time and prove it to be NP-hard. To address the conflicts between different multicast flows under the bandwidth constraint, we consider the concept of splitting multicast flows and propose a two round matching algorithm. Additionally, to further reduce the average completion time, we introduce a method to utilize the remaining capacity of the ToR switches by splitting the unscheduled flows. The proposed algorithm is proved to have an approximation ratio of $2\\sqrt{2n}$, where $n$ represents the number of Top-of-Rack (ToR) switches. Finally, the extensive simulations demonstrate the effectiveness of the proposed algorithm in reducing the average completion time of flows compared to state-of-the-art algorithms.","manuscriptTitle":"Towards Real-Time Non-Preemptive Multicast Scheduling in Reconfigurable Data Center Networks","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-01-08 06:33:14","doi":"10.21203/rs.3.rs-3825114/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2024-06-26T16:55:50+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-01-29T08:35:49+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"c08b9698-2981-40b5-82dd-4684c53ab590","date":"2024-01-22T08:13:25+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"e002e2f1-a395-41dc-adaa-abe15ac5eb62","date":"2024-01-22T06:20:47+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2024-01-22T03:18:25+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2024-01-18T00:48:22+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-01-05T10:50:55+00:00","index":"","fulltext":""},{"type":"submitted","content":"Peer-to-Peer Networking and Applications","date":"2023-12-31T03:55:48+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"peer-to-peer-networking-and-applications","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"ppna","sideBox":"Learn more about [Peer-to-Peer Networking and Applications](http://link.springer.com/journal/12083)","snPcode":"12083","submissionUrl":"https://submission.nature.com/new-submission/12083/3","title":"Peer-to-Peer Networking and Applications","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"d75a1d66-6caf-47a2-a3f9-74d0ae77be71","owner":[],"postedDate":"January 8th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2024-09-16T16:06:15+00:00","versionOfRecord":{"articleIdentity":"rs-3825114","link":"https://doi.org/10.1007/s12083-024-01804-w","journal":{"identity":"peer-to-peer-networking-and-applications","isVorOnly":false,"title":"Peer-to-Peer Networking and Applications"},"publishedOn":"2024-09-12 15:58:19","publishedOnDateReadable":"September 12th, 2024"},"versionCreatedAt":"2024-01-08 06:33:14","video":"","vorDoi":"10.1007/s12083-024-01804-w","vorDoiUrl":"https://doi.org/10.1007/s12083-024-01804-w","workflowStages":[]},"version":"v1","identity":"rs-3825114","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-3825114","identity":"rs-3825114","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}