Tek Paket Mesajlar İçin Aktarım Hızı Bozulmaları

Network Working Group — H. Opderbeck
Request for Comments: #632
UCLA-NMC
NIC #: 30239
20 Mayıs 1974

ARPANET üzerinden sayısallaştırılmış konuşmanın iletimi, paket anahtarlamalı sistemlerin kullanımında yeni bir boyutu temsil etmektedir. Bu yeni ortaya çıkan uygulama alanı için gereken aktarım hızı ve gecikme gereksinimleri, etkileşimli kullanım ya da dosya aktarımları için gereken aktarım hızı ve gecikme gereksinimlerinden oldukça farklıdır. Özellikle, küçük mesajlar için yüksek bir aktarım hızına ulaşmamız gerekmektedir; çünkü uzun mesajlar, büyük tamponların doldurulması için uzun kaynak gecikmelerine yol açmaktadır. Bu nedenle şu anda tek paketli mesajlar için aktarım hızı sınırlarını incelemekteyiz. Şimdiye kadar düşük gecikmeli trafik için aktarım hızını iyileştirmeye yönelik çok az çaba gösterildiğinin farkındayız. Buna rağmen, tek paketli mesajlar için gözlemlenen aktarım hızının birçok durumda beklenenin yalnızca yaklaşık dörtte biri olduğunu görmek bizim için şaşırtıcı olmuştur. Aşağıda bunun neden böyle olduğunu ve bu durumu düzeltmek için neler yapılabileceğini açıklayacağız.

1 Nisan 1974 tarihinde, IMP mesaj üretecini kullanarak, MOFFET-IMP’den SRI-IMP’ye mümkün olan en yüksek hızda ("RFNM güdümlü") tek paketli mesajlar gönderdik. MOFFET’ten SRI’ya iki adet üç sıçramalı yol bulunmaktadır; bunlardan biri iki adet 230,4 kbs devre içermektedir. Neredeyse hiç etkileşen trafik olmadığından, ortalama gidiş-dönüş gecikmesinin 100 ms’den fazla olmamasını bekliyorduk. MOFFET ile SRI arasında iletim halinde ortalama 3 mesaj bulunduğunu ve mesaj uzunluğunun yaklaşık 1000 bit olduğunu varsayarsak, bunun 30 kbs’den fazla bir aktarım hızıyla sonuçlanması gerekir. Ancak gözlemlenen aktarım hızı 8 kbs’den azdı. Deneyin tekrarlanması da aynı sonucu gösterdi. Toplanan verilerin daha ayrıntılı bir analizi, MOFFET ile SRI arasında eşzamanlı olarak iletim halinde ortalama 3,5 mesaj bulunduğunu ortaya koydu. Dolayısıyla aktarım hızı bozulması bu iki site arasındaki etkileşen trafikten kaynaklanmış olamazdı. Ayrıca, iletimde yer alan tüm kanallar için kanal kullanımı yüzde 40’tan azdı. Buna karşılık, MOFFET ile SRI arasındaki gözlemlenen ortalama gidiş-dönüş süreleri yaklaşık 500 ms idi. Bu büyük gidiş-dönüş sürelerinin açıkça fiziksel sınırlamalardan kaynaklanmadığı görüldüğünden, tek paketli mesajlar için akış denetimi mekanizmasını inceledik ve bu istenmeyen davranış için bir açıklama bulabildik.

Tek paketli bir mesaj hedef IMP’ye sırasız olarak ulaştığında (yani, mantıksal olarak bir önceki mesaj henüz oraya ulaşmamışsa) hedef IMP tarafından kabul edilmez. Bunun yerine, bir yeniden birleştirme tamponu tahsisi isteği olarak ele alınır. İlgili ALLOCATE mesajı ise, bir önceki mesaj için RFNM işlendiikten sonra kaynak IMP’ye geri gönderilir. Bu nedenle aşağıdaki olay dizisi gerçekleşebilir:

1. MSG(i) SOURCE-IMP’den gönderilir (mesaj i, kaynak IMP’den hedef IMP’ye gönderilir).
2. MSG(i+1) SOURCE-IMP’den gönderilir.
3. MSG(i+1) DEST-IMP’ye ulaşır (alternatif bir yol veya bir hat hatası nedeniyle, mesaj (i+1) hedef IMP’ye sırasız olarak ulaşır; bir yeniden birleştirme tamponu tahsisi isteği olarak ele alınır ve ardından atılır).
4. MSG(i) DEST-IMP’ye ulaşır (mesaj i hedef IMP’ye ulaşır; uygun HOST çıkış kuyruğuna konur).
5. RFNM(i) DEST-IMP’den gönderilir (mesaj i hedef HOST tarafından kabul edildikten sonra RFNM kaynak IMP’ye gönderilir).
6. ALL(i+1) DEST-IMP’den gönderilir (yalnızca mesaj i için RFNM işlendiikten sonra mesaj i+1 için ALLOCATE gönderilebilir).
7. RFNM(i) SOURCE-IMP’ye ulaşır.
8. ALL(i+1) SOURCE-IMP’ye ulaşır.
9. MSG(i+1) DEST-IMP’ye ulaşır (artık mesaj i+1 uygun HOST çıkış kuyruğuna konur).
10. RFNM(i+1) DEST-IMP’den gönderilir.
11. RFNM(i+1) SOURCE-IMP’ye ulaşır.

Dikkat edilmelidir ki mesaj i+1 için gidiş-dönüş süresi, olay 2 ile olay 11 arasındaki zaman aralığıdır. Dolayısıyla, diğer koşullar değişmediği sürece, mesaj i+1 için gidiş-dönüş süresi, sıralı olarak ulaşmış olsaydı olacağından iki katından daha fazladır. Bu nedenle bir hat hatası, birçok durumda yalnızca hatalı mesajı değil, aynı zamanda bir önceki mesajı 125 ms içinde izleyen bir sonraki tek paketli mesajı da geciktirir; bu süre hata yeniden iletim zaman aşımı aralığıdır. Ayrıca, hedef IMP’ye giden daha hızlı bir alternatif yol, mesajların oraya sırasız ulaşmasına neden olduğu için iletimi aslında yavaşlatabilir.

Bu durumu RFNM güdümlü tek paketli mesaj trafiğini ele aldığımızda daha da kötüleşir. Tablo 1, olası bir olay dizisini göstermektedir. Yine mesaj i+1’in hedef IMP’ye mesaj i’den önce ulaştığını varsayıyoruz.

Tablo 1. Mevcut Akış Denetimi Şeması İçin Yeniden İletim Deseni

(Trafik RFNM güdümlü olduğundan, RFNM i, i+1, ...’in varışı, mesaj i+4, i+5, ...’in gönderilmesiyle izlenir.)

Bu olay dizisiyle ilgili en ilginç gerçek, mesaj i+1’in hedef IMP’ye mesaj i’den önce ulaşmasının yalnızca mesaj i+1’in değil, gelecekteki tüm mesajların yeniden iletilmesine neden olmasıdır — gelecekteki mesajların hiçbirinin sırasız ulaştığını varsaymıyor olmamıza rağmen. Tablo ayrıca, mesaj i+4 ve ondan sonraki tüm mesajlar için gidiş-dönüş sürelerinin, bu istenmeyen yeniden iletimler olmasaydı olacağından dört kattan fazla olduğunu da göstermektedir. Ayrıca dikkat çekicidir ki, bu yeniden iletim deseni bir kez yerleştiğinde, kaynak IMP’deki giriş akışı kesilmedikçe sistemin bu durumdan kurtulmasının neredeyse hiçbir yolu yoktur. Örneğin, daha sonraki herhangi bir kullanıcı ya da denetim mesajının tek bir kez bile sırasız ulaşması bu yeniden iletim desenini değiştirmeyecektir. Tek paketli mesajların normal akışı ancak örneğin mesaj i+4, i+5 ve i+6’nın aynı anda birkaç yüz milisaniye gecikmesi ve bu sırada mesaj i+1, i+2 ve i+3’ün yeniden iletilebilmesi durumunda yeniden kurulabilir. Ancak böyle bir olayın gerçekleşme olasılığı son derece düşüktür. Bu nedenle sistemin bu istenmeyen yeniden iletim durumuna hapsolduğunu düşünebiliriz. Öte yandan mesajların “normal” akışı, sistemin yalnızca geçici davranışını temsil eder; çünkü iletim hataları nedeniyle iki mesajın sırasız ulaşması için her zaman sonlu bir olasılık vardır.

Daha önce de belirtildiği gibi, sistem bu aktarım hızı (ve gecikme) bozulmasından yalnızca tek paketli mesajların giriş akışı kesildiğinde kurtulabilir. Ancak konuşma iletimi durumunda bu, uzun bir süre boyunca gerçekleşmeyebilir. Bu nedenle konuşma iletim sistemleri, birçok durumda beklenen tek paketli bant genişliğinin yalnızca dörtte biriyle çalışmak zorunda kalacaktır. Bu açıkça kabul edilemez bir durum olduğundan, bu durumu düzelten mevcut akış denetimi şemasında bir değişiklik aradık. Aşağıda, mesajların istenmeyen yeniden iletimini önlemek için kullanılabilecek iki yöntemi açıklıyoruz.

Hatırlanacağı üzere, bir tek paketli mesaj, bir önceki mesaj için RFNM henüz kaynak IMP’ye gönderilmemişse, hedef IMP’de reddedilir ve daha sonra yeniden iletilir. Bu, esas olarak yeniden birleştirme kilitlenmesi koşullarının ortaya çıkmasını önlemek için yapılmaktadır [1]. Bu nedenle sorun, tüm tek paketli mesajları ek önlemler olmaksızın kabul ederek çözülemez; çünkü bu, kilitlenmeleri önleyecek mekanizmaların yokluğunda yeniden birleştirme kilitlenmesine yol açabilir. Birden fazla kaynak IMP’den gelen çok sayıda tek paketli mesajın ortak bir hedef IMP’ye sırasız ulaşması durumunda, hedef IMP yeniden birleştirme tamponlarının yetersizliği nedeniyle sıralı olan mesajları kabul edemeyebilir. Sonuç olarak sistem kilitlenir. Aktarım hızı bozulması sorununa getirilecek herhangi bir çözüm, sıralı olarak ulaşan tüm mesajların hedef IMP tarafından kabul edilebilmesini garanti etmelidir.

Bu amaca ulaşmanın bir yolu, sırasız ulaşan tek paketli mesajları yalnızca bir önceki mesaj(lar)ın tampon gereksinimi(leri) bilinmiyorsa reddetmektir. Önceki örneklerde, hedef IMP’nin, önce teslim edilmesi gereken mesajların tampon gereksinimlerini bilmesine rağmen mesajları sürekli olarak reddettiğini gördük. Tampon gereksinimleri bilinir hale geldikçe, gerekli sayıda tampon ayrılabilir ve gelecekteki tek paketli mesajlar kilitlenme tehlikesi olmaksızın kabul edilebilir. Böylece istenmeyen yeniden iletim deseni yerleşemez. Tablo 2, mesaj i+1’in hedef IMP’ye mesaj i’den önce ulaştığı durumda bu politikanın olay dizisini göstermektedir.

Tablo 2. Değiştirilmiş Akış Denetimi Şeması İçin Olay Dizisi

Bu değiştirilmiş şemada yalnızca tek bir mesajın, mesaj i+1’in, yeniden iletildiğine dikkat edilmelidir. Ancak IMP’lerin bol miktarda yeniden birleştirme tampon alanına sahip olduğu göz önüne alındığında, bu tek yeniden iletimin bile önlenmesi arzu edilir. Bu, özellikle sabit bir veri akışına bağlı olan ve ani büyük bir gecikme ile bozulacak olan konuşma iletimi için önemlidir. Bu nedenle, çoğu durumda herhangi bir yeniden iletim gerektirmeyecek olan aktarım hızı bozulması sorununu çözmek için ikinci bir yöntem öneriyoruz.

Tüm tek paketli mesajların başlangıçta kabul edildiğini (ya da saklandığını) varsayalım. Günümüzde sırasız ulaşan tek paketli mesajlar, kilitlenme olasılığı nedeniyle reddedilmektedir. Ancak tüm tek paketli mesajların kabul edildiği (ya da saklandığı) ve böylece bir sonraki HOST(lar)ına teslim edilmesi gereken mesajlar için yeniden birleştirme tamponu kalmadığı duruma daha yakından bakalım. Bu aslında bir kilitlenme durumu değildir; çünkü kaynak IMP’ler, RFNM henüz alınmamış olan tüm tek paketli mesajların bir kopyasını saklamaktadır. Dolayısıyla, sırasız ulaşıp yine de hedef IMP tarafından kabul edilen herhangi bir tek paketli mesaj, mesaj kaybolmadan daha sonra silinebilir. Hedef IMP’nin yapması gereken tek şey, yeniden birleştirme tampon alanı kullanılabilir hale geldiğinde silinen her tek paketli mesaj için ilgili kaynak IMP’ye bir ALLOCATE göndermektir. Bu, ertelenmiş reddetme olarak da düşünülebilir. Ancak bu durumda yeniden iletim, yalnızca hedef IMP gerçekten yeniden birleştirme tamponları tükenmek üzereyse gerekli olur. Bu noktada sistemin fiziksel sınırlamalarına ulaşılmıştır ve protokol değişiklikleri yoluyla büyük aktarım hızı artışları elde etmeyi bekleyemeyiz.

Bu konuyu gelecekte BBN’deki IMP geliştirme grubu ile sürdürmeyi amaçlıyoruz. Önerdiğimiz iki çözümün durumu iyileştireceği konusunda hemfikirdirler. Bununla birlikte, alternatif çözümler de düşünebilmektedirler.

Bu aktarım hızı bozulmasının keşfine yol açan deneylerin gerçekleştirilmesinde Bill Naylor ve Joe Katz’ın yardımlarını takdirle anıyorum.

Kaynaklar

1. Kleinrock, L. ve H. Opderbeck. "Mesaj Sıralaması Nedeniyle IMP Alt Ağında Olası Bir Kilitlenme Koşulu Üzerine", RFC #626.

Bu RFC, çevrimiçi RFC arşivlerine giriş için makine tarafından okunabilir biçime, daha önce BBN Corp. olarak bilinen GTE’nin desteğiyle Alex McKenzie tarafından 11/99 tarihinde dönüştürülmüştür.