Scheduling and queue management for information freshness in multi-source status update systems
Çok kaynaklı bilgi güncelleme sistemlerinde bilgi tazeliği için çizelgeleme ve kuyruk yönetimi
- Tez No: 831144
- Danışmanlar: PROF. DR. NAİL AKAR
- Tez Türü: Doktora
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2023
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 143
Özet
Bilginin hedeflenen yere zamanında ulaştırılması, mevcut ve gelişmekte olan zamana duyarlı uygulamaların birçoğunda oldukça önemlidir. Gecikme, veri hızı veya kayıp gibi geleneksel performans ölçütleri literatürde kapsamlı bir şekilde incelenmiş olsa da, yaşa duyarlı trafiğin yönetimine ilişkin araştırmalar nispeten olgunlaşmamıştır. Son zamanlarda, yaşa duyarlı trafik taşıyan ağ bağlantılı sistemlerde bilginin güncelliğini ölçmek için başta Bilgi Yaşı (AoI) ve zirve AoI (PAoI) ölçütleri olmak üzere Senkronizasyon Yaşı (AoS), sürüm yaşı, ikili tazelik gibi alternatiflerin de dahil olduğu birçok bilgi tazeliği ölçütü tanıtılmıştır. Bu tezin odak noktası, yakın geçmişte önerilmiş bilgi tazeliği ölçütlerini kullanarak yaşa duyarlı trafik taşıyan çeşitli çok kaynaklı durum güncelleme sistemlerinde yaş-agnostik çizelgeleme ve kuyruk yönetimi politikalarının geliştirilmesi ve performans modellemesidir. Bu tezde, ilk olarak, olasılıksal İsteğe-Bağlı-Üretim (GAW) ve Tek Tamponlu Rastgele Varış (RA-SB) sunucuları için AoI ve PAoI ölçütlerinin kesin dağılımları, faz tipi (PH tipi) hizmet süresi dağılımlarına sahip genel sayıda heterojen bilgi kaynağı ile incelenmiş ve bunun için AMC (Emici Markov Zincirleri) yöntemi olarak adlandırılan emici Sürekli Zaman Markov Zincirleri (CTMC) tabanlı bir analitik modelleme yöntemi önerilmiştir. İkinci olarak, Poisson bilgi paketi varışlarına ve üstel dağılımlı hizmet sürelerine sahip homojen çok kaynaklı bir durum güncelleme sistemi üzerinde çalışılmıştır; bu sistemde sunucu, Kaynak Başına Tek Tampon Kuyruklama (SBPSQ) olarak adlandırılan her kaynaktan gelen en güncel paketi tutan bir kuyruk ile donatılmıştır. Bu durum için, AMC yöntemi kullanılarak İlk Kaynak İlk Hizmet (FSFS) ve En Erken Hizmet Verilen İlk Hizmet (ESFS) politikaları olmak üzere iki SBPSQ tabanlı çizelgeleme politikası incelenmiş ve ESFS'nin bu özel durum için uygun bir çizelgeleyici olduğu gösterilmiştir. Üçüncü olarak, Deterministik GAW (D-GAW) ve Deterministik RA-SB (D-RA-SB) sunucuları için iki heterojen bilgi kaynağına sahip genel bir durum güncelleme sistemi incelenmiştir, yani kaynaklar farklı önceliklere ve genel dağılımlı hizmet sürelerine sahiptir. Her iki sunucuda da amaç, zaman ortalaması alınmış ve iki kaynak arasında ağırlıklandırılmış sistem AoI/AoS'yi en aza indirmektir. D-GAW sunucusu için optimal güncelleme politikası kapalı formda edilmiştir. Daha sonra, D-RA-SB sunucusu için, D-GAW sunucusunun optimal politika yapısına dayanan Örüntü Tabanlı Değiştirme (PR) politikası olarak isimlendirilmiş bir paket değiştirme politikası önerilmiştir. Son olarak, uzak bir sunucunun heterojen popülerliklere ve hizmet sürelerine sahip birden fazla öğenin zamanla değişen içeriğini, sistemin ağırlıklı toplam ikili tazeliğini en üst düzeye çıkarmak için yerel bir önbelleğe teslim ettiği ve sunucunun her öğe için en güncel içeriği tutan bir kuyrukla donatıldığı bir önbellek güncelleme sisteminde çizelgeleme incelenmiştir. Orijinal sistem kısıtlarının gevşetildiği bir duruma uygulanan dışbükey optimizasyona dayalı bir Su-doldurma tabanlı Çizelgeleme (WFS) politikası ve bunun uzantısı olan Genişletilmiş WFS (E-WFS) politikası önerilmiş olup, bu iki politika düşük hesaplama karmaşıklığı ve neredeyse optimal ağırlıklı toplam ikili tazelik performansına sahiptir.
Özet (Çeviri)
Timely delivery of information to its intended destination is essential in many existing and emerging time-sensitive applications. While conventional performance metrics like delay, throughput, or loss have been extensively studied in the literature, research concerning the management of age-sensitive traffic is relatively immature. Recently, a number of information freshness metrics have been introduced for quantifying the timeliness of information in networked systems carrying age-sensitive traffic, primarily the Age of Information (AoI) and peak AoI (PAoI) metrics as well as their alternatives including Age of Synchronization (AoS), version age, binary freshness, etc. The focus of this thesis is the development and performance modeling of age-agnostic scheduling and queue management policies in various multi-source status update systems carrying age-sensitive traffic, using the recently introduced information freshness metrics. In this thesis, first, the exact distributions of the AoI and PAoI for the probabilistic Generate-At-Will (GAW) and Random Arrival with Single Buffer (RA-SB) servers are studied with general number of heterogeneous information sources with phase-type (PH-type) service time distributions for which an absorbing Continuous-Time Markov Chains (CTMC) based analytical modeling method, namely AMC (Absorbing Markov Chains) method, is proposed. Secondly, a homogeneous multi-source status update system with Poisson information packet arrivals and exponentially distributed service times is studied for which the server is equipped with a queue holding the freshest packet from each source referred to as Single Buffer Per-Source Queueing (SBPSQ). For this case, two SBPSQ-based scheduling policies are studied, namely First Source First Serve (FSFS) and the Earliest Served First Serve (ESFS) policies, using the AMC method, and it is shown that ESFS presents a promising scheduler for this special setting. Third, a general status update system with two heterogeneous information sources is studied, i.e., sources have different priorities and generally distributed service times, for Deterministic GAW (D-GAW) and Deterministic RA-SB (D-RA-SB) servers. The aim in both servers is to minimize the system AoI/AoS that is time-averaged and weighted across the two sources. For the D-GAW server, the optimal update policy is obtained in closed form. A packet replacement policy, referred to as Pattern-based Replacement (PR) policy, is then proposed for the D-RA-SB server based on the optimal policy structure of the D-GAW server. Finally, scheduling in a cache update system is investigated where a remote server delivers time-varying contents of multiple items with heterogeneous popularities and service times to a local cache so as to maximize the weighted sum binary freshness of the system, and the server is equipped with a queue that holds the most up-to-date content for each item. A Water-filling based Scheduling (WFS) policy and its extension, namely Extended WFS (E-WFS) policy, are proposed based on convex optimization applied to a relaxation of the original system, with low computational complexity and near optimal weighted sum binary freshness performance.
Benzer Tezler
- Atölye tipi üretim için modüler çizelgeleme ve kontrol paketi
Modular scheduling and control package for job shop production
EMİN GÜNDOĞAR
Doktora
Türkçe
1991
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. MURAT DİNÇMEN
- New approaches for quality of service provisioning in cognitive radio networks
Bilişsel radyo ağlarında servis kalitesini yükseltmeye yönelik yeni yaklaşımlar
GÜLNUR SELDA UYANIK
Doktora
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. SEMA FATMA OKTUĞ
- Atölyede iş çizelgeme
Operations scheduling in job shops
GÖKHAN KIPÇAK
Yüksek Lisans
Türkçe
1990
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. ATAÇ SOYSAL
- Malzeme ihtiyaç planlaması ve üretim kaynakları planlaması
Material reouirements planning and manufacturing resource planning
RASİM CÜNEYT GENÇ
- Bir kablo donanım üretim sisteminde tam zamanında üretim uygulaması
Just in time application in a wiring assemblies and harneses production systems
MİNE AKSOY
Yüksek Lisans
Türkçe
1997
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. M. BÜLENT DURMUŞOĞLU