{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/16940"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/16940","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Robustness in large-scale random networks","abstract":"We consider the issue of protection in very large networks displaying randomness in topology. We employ random graph models to describe such networks, and obtain probabilistic bounds on several parameters related to various protection schemes. In particular, we take the case of random regular networks for simplicity, where the degree of each node is the same, and consider the length of primary and backup paths in terms of the number of hops. First, for a randomly picked pair of nodes, we derive a lower bound on the average distance between the pair and discuss the tightness of the bound. In addition, noting that primary and protection paths form cycles, we obtain a lower bound on the average length of the shortest cycle around the pair. Finally, we show that the protected connections of a given maximum finite length are rare. We then generalize our network model so that different degrees are allowed according to some arbitrary distribution. Notably, we derive an upper bound on the mean number of non-finite length cycles in generalized random networks. More importantly, we show that most of the results in regular networks carry over with minor modifications, which significantly broadens the scope of networks to which our approach applies. Our main contributions are the following. First, we take an analytical approach by bringing the concept of randomness into network topologies that can provide concise rules to relate basic network parameters to robustness. Second, we establish analytical results for the length of backup paths for path and link-based protection schemes rather than for the efficiency of backup capacity, upon which most studies concentrate. Finally, we develop a unified framework for studying the issue of robustness in very general random networks with arbitrary degree distributions.","abstract_html":"We consider the issue of protection in very large networks displaying randomness in topology. We employ random graph models to describe such networks, and obtain probabilistic bounds on several parameters related to various protection schemes. In particular, we take the case of random regular networks for simplicity, where the degree of each node is the same, and consider the length of primary and backup paths in terms of the number of hops. First, for a randomly picked pair of nodes, we derive a lower bound on the average distance between the pair and discuss the tightness of the bound. In addition, noting that primary and protection paths form cycles, we obtain a lower bound on the average length of the shortest cycle around the pair. Finally, we show that the protected connections of a given maximum finite length are rare. We then generalize our network model so that different degrees are allowed according to some arbitrary distribution. Notably, we derive an upper bound on the mean number of non-finite length cycles in generalized random networks. More importantly, we show that most of the results in regular networks carry over with minor modifications, which significantly broadens the scope of networks to which our approach applies. Our main contributions are the following. First, we take an analytical approach by bringing the concept of randomness into network topologies that can provide concise rules to relate basic network parameters to robustness. Second, we establish analytical results for the length of backup paths for path and link-based protection schemes rather than for the efficiency of backup capacity, upon which most studies concentrate. Finally, we develop a unified framework for studying the issue of robustness in very general random networks with arbitrary degree distributions.","abstract_has_math":false,"creators":["Kim, Minkyu, 1976-"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Muriel Médard."],"committee_chairs":[],"committee_members":[],"year":2003,"date_issued":"2003","date_published":"2003","updated_at":"2026-07-22T22:22:11Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/16940","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Muriel Médard."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Kim, Minkyu, 1976-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2005-05-19T15:22:03Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2005-05-19T15:22:03Z"]},{"key":"dc:date.issued","label":"Date","values":["2003"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/16940"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.","Includes bibliographical references (p. 73-76).","This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections."]},{"key":"dc:description.abstract","label":"Abstract","values":["We consider the issue of protection in very large networks displaying randomness in topology. We employ random graph models to describe such networks, and obtain probabilistic bounds on several parameters related to various protection schemes. In particular, we take the case of random regular networks for simplicity, where the degree of each node is the same, and consider the length of primary and backup paths in terms of the number of hops. First, for a randomly picked pair of nodes, we derive a lower bound on the average distance between the pair and discuss the tightness of the bound. In addition, noting that primary and protection paths form cycles, we obtain a lower bound on the average length of the shortest cycle around the pair. Finally, we show that the protected connections of a given maximum finite length are rare. We then generalize our network model so that different degrees are allowed according to some arbitrary distribution. Notably, we derive an upper bound on the mean number of non-finite length cycles in generalized random networks. More importantly, we show that most of the results in regular networks carry over with minor modifications, which significantly broadens the scope of networks to which our approach applies. Our main contributions are the following. First, we take an analytical approach by bringing the concept of randomness into network topologies that can provide concise rules to relate basic network parameters to robustness. Second, we establish analytical results for the length of backup paths for path and link-based protection schemes rather than for the efficiency of backup capacity, upon which most studies concentrate. Finally, we develop a unified framework for studying the issue of robustness in very general random networks with arbitrary degree distributions."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Robustness in large-scale random networks"]}]}],"canonical_facts":{"dc:contributor.advisor":["Muriel Médard."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Kim, Minkyu, 1976-"],"dc:date.accessioned":["2005-05-19T15:22:03Z"],"dc:date.available":["2005-05-19T15:22:03Z"],"dc:date.issued":["2003"],"dc:description":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.","Includes bibliographical references (p. 73-76).","This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections."],"dc:description.abstract":["We consider the issue of protection in very large networks displaying randomness in topology. We employ random graph models to describe such networks, and obtain probabilistic bounds on several parameters related to various protection schemes. In particular, we take the case of random regular networks for simplicity, where the degree of each node is the same, and consider the length of primary and backup paths in terms of the number of hops. First, for a randomly picked pair of nodes, we derive a lower bound on the average distance between the pair and discuss the tightness of the bound. In addition, noting that primary and protection paths form cycles, we obtain a lower bound on the average length of the shortest cycle around the pair. Finally, we show that the protected connections of a given maximum finite length are rare. We then generalize our network model so that different degrees are allowed according to some arbitrary distribution. Notably, we derive an upper bound on the mean number of non-finite length cycles in generalized random networks. More importantly, we show that most of the results in regular networks carry over with minor modifications, which significantly broadens the scope of networks to which our approach applies. Our main contributions are the following. First, we take an analytical approach by bringing the concept of randomness into network topologies that can provide concise rules to relate basic network parameters to robustness. Second, we establish analytical results for the length of backup paths for path and link-based protection schemes rather than for the efficiency of backup capacity, upon which most studies concentrate. Finally, we develop a unified framework for studying the issue of robustness in very general random networks with arbitrary degree distributions."],"dc:description.degree":["S.M."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/1721.1/16940"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Robustness in large-scale random networks"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:22:11Z"}