Weak state and its evaluation for routing in large scale dynamic networks
Başlık çevirisi mevcut değil.
- Tez No: 401543
- Danışmanlar: PROF. ALHUSSEIN A. ABOUZEID, PROF. SHIVKUMAR KALYANARAMAN
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2009
- Dil: İngilizce
- Üniversite: Rensselaer Polytechnic Institute
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 198
Özet
Özet yok.
Özet (Çeviri)
Routing protocols in communication networks rely on routing table entries (“states”) to make decisions on how to forward packets. The routing table state typically maps an ID (eg: destination address) to a locator. The locator specifies how to reach the node with the given ID. If paths to a node change, the states corresponding to the ID of the node become invalid. For resilient routing, states should always be up-to-date. As the network size increases and it becomes more dynamic, most routing table entries at every router must be updated. A natural consequence is the huge increase in control traffic that crowds out the network capacity. For such large and dynamic networks, we propose to use probabilistic routing tables, where routing table entries are considered as a probabilistic hints (called weak state), and not absolute truth. Weak state can be locally refreshed (i.e. without the need for explicit control traffic or updates that traverse the network) by reducing the associated confidence value, a measure of the probability that the state is accurate. We build routing protocols using the concept of weak state for mobile ad-hoc networks (MANETs) and delay tolerant networks (DTNs). For MANETs, we propose the Weak State Routing (WSR) protocol that uses the concept of random directional walks (i.e. walks in randomly chosen directions) as a primitive both for disseminating weak state, and for forwarding packets. In particular, when a random directional walk for forwarding a packet reaches a node, it consults the weak-state at the node, and biases its walk direction if the node has stronger information (in terms of confidence) about the destination location. In DTNs, an additional challenge is that a complete path may never exist between a source-destination pair and routing is achieved by the store-carry-forward paradigm. Intermittent connectivity also prevents the control messages from diffusing in the network. Hence, it is difficult to maintain consistent routing states. We propose Weak State Routing protocol for Delay Tolerant Networks (WSR-D) that uses explicit mappings with xix weak states. Weak state is particularly useful for DTNs because it has probabilistic semantics and can be refreshed locally. WSR-D disseminates weak state using a local osmosis mechanism. It employs a biasing technique similar to that of WSR. WSR-D exploits node mobility rather than node positions. A packet is forwarded to an intermediate node only if it is moving in a direction closer to the direction given by the biasing weak state. Our simulation results show that WSR offers a high packet delivery ratio, more than 98%. Protocol overhead scales as O(N), N being the number of nodes. The state complexity of the protocol is (N3=2). Even though packets follow paths longer than the shortest paths, the average path length is asymptotically efficient and scales as O(p N). Despite longer paths, WSRs end-to-end packet delivery delay is much smaller than the prior work because of the dramatic reduction in control traffic overhead. WSR-D achieves very high delivery ratio even when the buffer space in the nodes is limited. It reduces the number of packet transfers between nodes in comparison to prior work at the cost of increased delay. We also investigate the effect of state weak-ness on the consistency of information. We define two metrics, pure distortion and informed distortion, to evaluate the consistency of the weak state paradigm and compare it against strong state (i.e. deterministic state that relies on explicit refresh messages to remain valid). Pure distortion measures the average gap between the actual value of the state and the value maintained at a remote node. On the other hand, the use of confidence increases the protocol's ability to cope with even large pure distortion. The resulting effective distortion is captured by the informed distortion metric. We analytically show that weak state causes significantly less distortion values than strong state. In the final part of this dissertation, we investigate the random walks on dynamic time-graphs. Random walks form the basis of the unstructured methods. We investigate the effect of dynamism in the network on the random walk performance, which is a strong indicator of network connectivity. Such networks are modeled by a novel 3-mode adjacency tensor. The expected hitting time of a random walk in a dynamic network is small if the network is well connected. The representation also leads to the information whether a node can be reached by another node after a certain number of time steps, which is indicated by reachability tensor. We unfold the reachability tensor around the mode or dimension that models time to obtain a matrix. Our experiments show that the correlation between the expected hitting time and the second singular-value of this matrix is above 0.95. Hence, it is a strong indicator of network connectivity.
Benzer Tezler
- Ticari banka yönetimi ve Türk ticari bankalarının temel yönetim sorunları
The management of the commercial bank and the basic problems of the Turkish comercial bank
AYŞE ÇİĞDEM ÖNAL
- Son dönem böbrek yetmezliği olup rutin hemodiyaliz tedavisi alan hastalarda serum ürik asit düzeyi ile karotis intima media kalınlığı arasındaki ilişkinin değerlendirilmesi
Evaluation of the relationship between serum uric acid level and carotid intima media thickness in patients with end-stage renal disease receiving routine hemodialysis treatment
HAMZA İNAN
Tıpta Uzmanlık
Türkçe
2023
İç HastalıklarıErzincan Binali Yıldırım Üniversitesiİç Hastalıkları Ana Bilim Dalı
DOÇ. DR. ALİ VEYSEL KARA
- Zeminlerin indeks özellikleri ve SPT-CPT deneylerinin karşılaştırılması
A Correlation study between standard penetration test and static cone penetration test results
ŞAFAK HATUNOĞLU
- Ankara Üniversitesi Tıp Fakültesi erişkin diyabet polikliniğine başvuran hastalarda tırnak batması görülme sıklığı, klinik ve laboratuvar özeliklerinin değerlendirilmesi
Prevalance, clinical features and evaluation of the risk factors for ingrown nails in adult diabetic patients in ambulatory service
SEÇİL SARAL
Tıpta Uzmanlık
Türkçe
2012
DermatolojiAnkara ÜniversitesiDeri ve Zührevi Hast. Ana Bilim Dalı
PROF. DR. SEHER BOSTANCI
PROF. DR. PELİN KOÇYİĞİT
- Osmanlı-Türk şehrinde mahalle
Mahalle in the ottoman Turkish city
ADALET BAYRAMOĞLU ALADA
Doktora
Türkçe
1989
Kamu YönetimiAnkara ÜniversitesiKamu Yönetimi ve Siyaset Bilimi Ana Bilim Dalı
PROF. DR. RUŞEN KELEŞ