{"id":12780,"date":"2021-11-21T16:48:17","date_gmt":"2021-11-21T21:48:17","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12780"},"modified":"2021-11-21T16:48:17","modified_gmt":"2021-11-21T21:48:17","slug":"tr-95-11-sense-of-direction-minimizing-congestion-of-layouts-for-atm-networks-with-faulty-links","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-11-sense-of-direction-minimizing-congestion-of-layouts-for-atm-networks-with-faulty-links\/","title":{"rendered":"TR-95-11: Sense of Direction: Minimizing Congestion of Layouts for ATM Networks with Faulty Links"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-95-11
\nMay 1995<\/p>\n

Minimizing Congestion of Layouts for ATM Networks with Faulty Links<\/h2>\n
\n
\n
\n
\n
Leszek Gasieniec, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n

We consider the problem of constructing virtual path layouts for an ATM network consisting of a complete network Kn of n processors in which a certain number of links may fail. Our main goal is to construct layouts which tolerate any con\fguration of up to f layouts and have the least possible congestion. First, we study the minimal congestion of 1-hop f-tolerant layouts in Kn. For any positive integer f we give upper and lower bounds on this minimal congestion and construct f-tolerant layouts with congestion corresponding to the upper bounds. Our results are based on a precise analysis of the diameter of the network Kn[F] which results from Kn by deleting links from a set F of bounded size. Next we study the minimal congestion of h-hop f- tolerant layouts in Kn, for larger values of the number h of hops. We give upper and lower bounds on the order of magnitude of this congestion, based on results for 1-hop layouts. Finally, we consider a random, rather than worst case, fault distribution. Links fail independently with constant probability p < 1. Our goal now is to construct layouts with low congestion that tolerate the existing faults with high probability. For any p < 1, we show such layouts in Kn, with congestion O(log n).<\/p>\n

TR-95-11.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-95-11 May 1995 Minimizing Congestion of Layouts for ATM Networks with Faulty Links Leszek Gasieniec, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc Abstract We consider the problem of constructing virtual path layouts for an ATM network consisting of a complete network Kn of n processors in which a certain number of links […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":11736,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"\nTR-95-11: Sense of Direction: Minimizing Congestion of Layouts for ATM Networks with Faulty Links - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-95-11 May 1995 Minimizing Congestion of Layouts for ATM Networks with Faulty Links Leszek Gasieniec, Evangelos\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-11-sense-of-direction-minimizing-congestion-of-layouts-for-atm-networks-with-faulty-links\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-11-sense-of-direction-minimizing-congestion-of-layouts-for-atm-networks-with-faulty-links\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-11-sense-of-direction-minimizing-congestion-of-layouts-for-atm-networks-with-faulty-links\/\",\"name\":\"TR-95-11: Sense of Direction: Minimizing Congestion of Layouts for ATM Networks with Faulty Links - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-21T21:48:17+00:00\",\"dateModified\":\"2021-11-21T21:48:17+00:00\",\"description\":\"Carleton University Technical Report TR-95-11 May 1995 Minimizing Congestion of Layouts for ATM Networks with Faulty Links Leszek Gasieniec, Evangelos\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-11-sense-of-direction-minimizing-congestion-of-layouts-for-atm-networks-with-faulty-links\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-11-sense-of-direction-minimizing-congestion-of-layouts-for-atm-networks-with-faulty-links\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-11-sense-of-direction-minimizing-congestion-of-layouts-for-atm-networks-with-faulty-links\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 1995\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-95-11: Sense of Direction: Minimizing Congestion of Layouts for ATM Networks with Faulty Links\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-95-11: Sense of Direction: Minimizing Congestion of Layouts for ATM Networks with Faulty Links - School of Computer Science","description":"Carleton University Technical Report TR-95-11 May 1995 Minimizing Congestion of Layouts for ATM Networks with Faulty Links Leszek Gasieniec, Evangelos","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-11-sense-of-direction-minimizing-congestion-of-layouts-for-atm-networks-with-faulty-links\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-11-sense-of-direction-minimizing-congestion-of-layouts-for-atm-networks-with-faulty-links\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-11-sense-of-direction-minimizing-congestion-of-layouts-for-atm-networks-with-faulty-links\/","name":"TR-95-11: Sense of Direction: Minimizing Congestion of Layouts for ATM Networks with Faulty Links - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-21T21:48:17+00:00","dateModified":"2021-11-21T21:48:17+00:00","description":"Carleton University Technical Report TR-95-11 May 1995 Minimizing Congestion of Layouts for ATM Networks with Faulty Links Leszek Gasieniec, Evangelos","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-11-sense-of-direction-minimizing-congestion-of-layouts-for-atm-networks-with-faulty-links\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-11-sense-of-direction-minimizing-congestion-of-layouts-for-atm-networks-with-faulty-links\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-11-sense-of-direction-minimizing-congestion-of-layouts-for-atm-networks-with-faulty-links\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 1995","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/"},{"@type":"ListItem","position":5,"name":"TR-95-11: Sense of Direction: Minimizing Congestion of Layouts for ATM Networks with Faulty Links"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12780"}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/49"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12780"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12780\/revisions"}],"predecessor-version":[{"id":12781,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12780\/revisions\/12781"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11736"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12780"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}