{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/9744"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/9744","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"Utility Accrual Real-time Channel Establishment in Multi-hop Networks","abstract":"Real-time channels are established between a source and a destination to guarantee in-time delivery of real-time messages in multi-hop networks. In this thesis, we propose two schemes to establish real-time channels for soft real-time applications whose timeliness properties are characterized using Jensen's Time Utility Functions (TUFs) that are non-increasing. The two algorithms are (1) Localized Decision for Utility accrual Channel Establishment (LocDUCE) and (2) Global Decision for Utility accrual Channel Establishment (GloDUCE). Since finding a feasible path optimizing multiple constraints is an NP-Complete problem, these schemes heuristically attempt to maximize the system-wide accrued utility. The channel establishment algorithms assume the existence of a utility-aware packet scheduling algorithm at the interfaces. The route selection is based on delay estimation performed at the source, destination, and all routers in the path, from source to destination. We simulate the algorithms, measure and compare their performance with open shortest path first (OSPF). Our simulation experiments show that for most of the cases considered LocDUCE and GloDUCE perform better than OSPF. We also implement the schemes in a proof-of-concept style routing module and measure the performance of the schemes and compare them to OSPF. Our experiments on the implementation follow the same trend as the simulation study and show that LocDUCE and GloDUCE have a distinct advantage over OSPF and accrue higher system-wide utility. These schemes also react better to variation in the loading of the links. Among the two proposed approaches, we observe that GloDUCE performs better than LocDUCE under conditions of increased downstream link loads.","abstract_html":"Real-time channels are established between a source and a destination to guarantee in-time delivery of real-time messages in multi-hop networks. In this thesis, we propose two schemes to establish real-time channels for soft real-time applications whose timeliness properties are characterized using Jensen's Time Utility Functions (TUFs) that are non-increasing. The two algorithms are (1) Localized Decision for Utility accrual Channel Establishment (LocDUCE) and (2) Global Decision for Utility accrual Channel Establishment (GloDUCE). Since finding a feasible path optimizing multiple constraints is an NP-Complete problem, these schemes heuristically attempt to maximize the system-wide accrued utility. The channel establishment algorithms assume the existence of a utility-aware packet scheduling algorithm at the interfaces. The route selection is based on delay estimation performed at the source, destination, and all routers in the path, from source to destination. We simulate the algorithms, measure and compare their performance with open shortest path first (OSPF). Our simulation experiments show that for most of the cases considered LocDUCE and GloDUCE perform better than OSPF. We also implement the schemes in a proof-of-concept style routing module and measure the performance of the schemes and compare them to OSPF. Our experiments on the implementation follow the same trend as the simulation study and show that LocDUCE and GloDUCE have a distinct advantage over OSPF and accrue higher system-wide utility. These schemes also react better to variation in the loading of the links. Among the two proposed approaches, we observe that GloDUCE performs better than LocDUCE under conditions of increased downstream link loads.","abstract_has_math":false,"creators":["Channakeshava, Karthik"],"institution":"Virginia Tech","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Electrical and Computer Engineering","degree_department":"Electrical and Computer Engineering","school":null,"contributors":[],"advisors":[],"committee_chairs":["Ravindran, Binoy"],"committee_members":["Nayfeh, Ali H.","Midkiff, Scott F.","Habayeb, Abdul-Razzaq R."],"year":2004,"date_issued":"2004-03-04","date_published":"2004-03-04","updated_at":"2026-07-22T22:19:53Z","subjects":["real-time","multi-hop networks","real-time systems"],"languages":[],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-03222004-173216"],"render_values":[{"text":"etd-03222004-173216","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/10919/9744","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeechair","label":"Committee Chair","values":["Ravindran, Binoy"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Nayfeh, Ali H.","Midkiff, Scott F.","Habayeb, Abdul-Razzaq R."]},{"key":"dc:contributor.department","label":"Department","values":["Electrical and Computer Engineering"]},{"key":"dc:creator","label":"Author","values":["Channakeshava, Karthik"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2011-08-06T14:47:18Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2011-08-06T14:47:18Z","2004-03-26"]},{"key":"dc:date.issued","label":"Date","values":["2004-03-04"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical and Computer Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["real-time","multi-hop networks","real-time systems"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-03222004-173216"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/9744"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Real-time channels are established between a source and a destination to guarantee in-time delivery of real-time messages in multi-hop networks. In this thesis, we propose two schemes to establish real-time channels for soft real-time applications whose timeliness properties are characterized using Jensen's Time Utility Functions (TUFs) that are non-increasing. The two algorithms are (1) Localized Decision for Utility accrual Channel Establishment (LocDUCE) and (2) Global Decision for Utility accrual Channel Establishment (GloDUCE). Since finding a feasible path optimizing multiple constraints is an NP-Complete problem, these schemes heuristically attempt to maximize the system-wide accrued utility. The channel establishment algorithms assume the existence of a utility-aware packet scheduling algorithm at the interfaces. The route selection is based on delay estimation performed at the source, destination, and all routers in the path, from source to destination. We simulate the algorithms, measure and compare their performance with open shortest path first (OSPF). Our simulation experiments show that for most of the cases considered LocDUCE and GloDUCE perform better than OSPF. We also implement the schemes in a proof-of-concept style routing module and measure the performance of the schemes and compare them to OSPF. Our experiments on the implementation follow the same trend as the simulation study and show that LocDUCE and GloDUCE have a distinct advantage over OSPF and accrue higher system-wide utility. These schemes also react better to variation in the loading of the links. Among the two proposed approaches, we observe that GloDUCE performs better than LocDUCE under conditions of increased downstream link loads."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science"]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["ETD"]},{"key":"dc:title","label":"Title","values":["Utility Accrual Real-time Channel Establishment in Multi-hop Networks"]}]}],"canonical_facts":{"dc:contributor.committeechair":["Ravindran, Binoy"],"dc:contributor.committeemember":["Nayfeh, Ali H.","Midkiff, Scott F.","Habayeb, Abdul-Razzaq R."],"dc:contributor.department":["Electrical and Computer Engineering"],"dc:creator":["Channakeshava, Karthik"],"dc:date.accessioned":["2011-08-06T14:47:18Z"],"dc:date.available":["2011-08-06T14:47:18Z","2004-03-26"],"dc:date.issued":["2004-03-04"],"dc:description.abstract":["Real-time channels are established between a source and a destination to guarantee in-time delivery of real-time messages in multi-hop networks. In this thesis, we propose two schemes to establish real-time channels for soft real-time applications whose timeliness properties are characterized using Jensen's Time Utility Functions (TUFs) that are non-increasing. The two algorithms are (1) Localized Decision for Utility accrual Channel Establishment (LocDUCE) and (2) Global Decision for Utility accrual Channel Establishment (GloDUCE). Since finding a feasible path optimizing multiple constraints is an NP-Complete problem, these schemes heuristically attempt to maximize the system-wide accrued utility. The channel establishment algorithms assume the existence of a utility-aware packet scheduling algorithm at the interfaces. The route selection is based on delay estimation performed at the source, destination, and all routers in the path, from source to destination. We simulate the algorithms, measure and compare their performance with open shortest path first (OSPF). Our simulation experiments show that for most of the cases considered LocDUCE and GloDUCE perform better than OSPF. We also implement the schemes in a proof-of-concept style routing module and measure the performance of the schemes and compare them to OSPF. Our experiments on the implementation follow the same trend as the simulation study and show that LocDUCE and GloDUCE have a distinct advantage over OSPF and accrue higher system-wide utility. These schemes also react better to variation in the loading of the links. Among the two proposed approaches, we observe that GloDUCE performs better than LocDUCE under conditions of increased downstream link loads."],"dc:description.degree":["Master of Science"],"dc:format.medium":["ETD"],"dc:identifier.other":["etd-03222004-173216"],"dc:identifier.uri":["http://hdl.handle.net/10919/9744"],"dc:publisher":["Virginia Tech"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:subject":["real-time","multi-hop networks","real-time systems"],"dc:title":["Utility Accrual Real-time Channel Establishment in Multi-hop Networks"],"dc:type":["Thesis"],"thesis:degree_discipline":["Electrical and Computer Engineering"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:19:53Z"}