Network Working Group — V. Cerf
Request for Comments: 442
NIC: 13774
Tarih: 24 Ocak 1973
IMPSYS için Mevcut Akış Denetimi Düzeni
BB&N üç aylık rapor #13, IMP işletim sistemindeki mevcut akış denetimi düzeninin bir bölümünü ana hatlarıyla açıklamaktadır. 16 Mart 1972 tarihinde BB&N’de yapılan bir toplantı, bu yeni düzenin ilgili ağ katılımcılarının yararına açıklanmasına ayrılmıştır.
Bu not, akış denetimi mekanizmasına ilişkin benim anlayışımı temsil etmektedir. Temel hedef; yük ağır olduğunda gereksiz yeniden iletimleri ortadan kaldırmak, yük hafif olduğunda yeniden iletim zaman aşımı süresini ortadan kaldırmak, bant genişliğini artırmak, yeniden birleştirme kilitlenmesini önlemek, HOST’lardan ağa giren trafiği önceki bağlantı engelleme yöntemine kıyasla daha sıkı denetlemek ve kendimiz ile gelecek kuşaklarımız için yaşam, özgürlük ve mutluluk arayışı haklarını güvence altına almaktır, …ops.
Kaynak IMP’den Hedef IMP’ye Protokol
İleti uzunluğuna bağlı olarak (yani tek paketli veya çok paketli) iki farklı protokol vardır. Önce tek paketli durumu gösteriyoruz.
Source IMP Destination IMP
---------- ---------------
case 1) message (1) + implicit req (1) --->
<--- RFNM (arrived ok)
[discard copy of msg]
case 2) message (1) + implicit req (1) ---> no room, don't respond
<--- ALL (1) (room available)
message (1) --->
[discard copy of msg] <--- RFNM (arrived ok)
Birinci durumda, tek paketli bir ileti hedef IMP’ye gönderilir. Bu ileti, tek paketlik arabellek alanı için örtük bir istek işlevi görür. Eğer yer varsa, durum 1’de olduğu gibi, hedef IMP bir RFNM ile yanıt verir. İletinin bir kopyasını elinde tutmuş olan kaynak IMP, kopyasını siler ve devam eder.
İkinci durum, kaynak IMP’nin, tek paketlik ileti için yer olmayan bir hedef IMP’ye ileti göndermesi halinde ne olduğunu göstermektedir. Tek paketli iletinin gelişi, tek paketlik arabellek alanı için bir istek oluşturur ve hedef IMP tarafından ilk gelen ilk hizmet alır esasına göre çalışan bir arabellek rezervasyon istek kuyruğuna bu şekilde kaydedilir. Yer kullanılabilir olduğunda, hedef IMP istekte bulunan kaynak IMP’ye bir ALL (1) gönderir; böylece kaynak IMP tek paketli iletiyi bu kez hedefte alanın rezerve edildiğini bilerek yeniden gönderebilir.
Çok paketli iletiler için yordam biraz farklıdır. Bir ileti bir HOST’tan bir IMP’ye girdiğinde ve azami uzunluktaki tek bir paketin bit sayısı ulaştığında “son bit” bayrağı ayarlı değilse, IMP, hedef IMP’de alanın rezerve edilip edilmediğini belirlerken HOST→IMP iletim hattını durdurur. Eğer alan (8 paketlik) rezerve edilmişse, HOST→IMP hattı yeniden açılır ve ileti normal şekilde gönderilir. Alan rezerve edilmemişse, kaynak IMP hedef IMP’de çok paketli arabellek depolaması için bir istek yaparken HOST→IMP hattı kapalı tutulur. 8 arabellek kullanılabilir olduğunda, hedef IMP bir ALL (8) ile yanıt verir. Kaynak IMP daha sonra iletiyi iletir ve hedef IMP’den bir RFNM ile örtük bir ALL (8) birleşimini bekler. Hedef IMP, gerekirse, bir sonraki çok paketli ileti için yeniden 8 arabellek kullanılabilir olana kadar RFNM’yi geciktirecektir.
Bu dizi aşağıda gösterilmiştir:
Source IMP Destination IMP
---------- ---------------
H->I line
----------> First packet of multipacket
arrives. Halt H->I line and
send REQ (8) -------------->
start 30 sec. time-out
If time-out, resend
REQ (8) and restart -------->
time-out.
<-------- ALL (8) when available. Start
long-term (2 min.) time-out.
On time-out, reset all
outstanding reservations.
Send the message:
| ----------->
Start 30 sec. time-out
for incomplete transmission.
If time-out, send INC? ----->
<------ On receipt of message, send
RFNM + implicit ALL (8). On
receipt of INC? send RFNM +
ALL (8) if MSG (8) received,
or send INC! if MSG (8) not
received. Start 2 min. time-out
on ALL (8).
Queue ALL (8); start 125 ms
time-out when it reaches
head of queue. If time-out
on ALL (8), send GVB (8) ---->
<----- Ack.
else send next message ----->
Bu protokoldeki kilit nokta şudur: Bir kaynak IMP, hedef IMP’den bir RFNM ve örtük bir ALL (8) aldıktan sonra, çok paketli bir iletinin en azından ilk paketinin hedef IMP’ye aktarımını başlatmak için 125 ms süresine sahiptir. Kaynak IMP’nin kuyrukta birden fazla tahsis yanıtı olabilir; bu durumda bu zaman aşımılar art arda gerçekleşir (birinin zaman aşımına uğraması gerekir ki bir sonraki 125 ms’lik zaman aşımı başlasın).
Kaynak IMP’de, daha önceki bir iletiden herhangi bir yanıt almamışsa hedef IMP’ye INC? iletileri göndermesine neden olan zaman aşımılar bulunmaktadır.
Arabellek Tahsisi
Depola/ilet ve yeniden birleştirme amaçları için toplam 40 arabellek kullanılabilir durumdadır. En fazla 32’si yeniden birleştirme için, en fazla 24–25’i ise depola-ve-ilet kullanımı için tahsis edilebilir. Bu, her iki tür trafiğin de diğerini tamamen dışlamasını önler.
İleti Sıralaması (Kaynak IMP’den Hedef IMP’ye)
Tıkanıklık denetimine yardımcı olmak amacıyla, bir IMP’nin her bir diğer IMP için en fazla 4 adet beklemede (RFNM alınmamış) iletisi olabilir. İleti başlığındaki bağlantı numaraları IMP’ler tarafından yok sayılır. Bunun yerine, IMP’ler diğer hedeflere giden iletileri 8 bitlik bir ileti numarasıyla işaretler. Ayrıca, bir HOST bir iletiyi öncelikli olarak işaretlemişse, 2 bitlik bir öncelik numarası da kullanılır. Buradaki temel kavram, IMP’lerin belirli bir IMP üzerindeki tüm HOST’ları tek bir HOST varmış gibi ele almasıdır. Her site çifti arasında her yönde tek bir ileti ve öncelik numarası dizisi kullanılır.
Alıcı IMP, teslim edilen son iletinin ileti numarasını ve teslim edilen son öncelikli iletinin öncelik numarasını hatırlar. Bu bilgiyi, iletileri IMP–HOST hattı/hatları üzerinden doğru sırayla çıkarmak için kullanır. Her site çifti için yalnızca tek bir sayı dizisi bulunduğundan, bir sitedeki bir HOST için olan iletiler, aynı sitedeki başka bir HOST için olan iletilerin önüne geçebilir. Gerçekten de, eğer bir ileti, m, belirli bir HOST’a gitmek üzere sıradaki bir sonraki iletiyse ve bu HOST alımı 30 saniye geciktirirse, başka bir HOST için olan iletiler de o kadar süre gecikebilir. Ancak yalnızca ilk ileti kaybolur; çünkü ikinci ileti, birincisi teslim edilmeden hedef HOST’a doğru ilerlemeye bile başlayamaz. Aynı IMP’yi paylaşan HOST’lar arasında önceye göre daha sıkı bir bağ vardır, ancak çok daha sıkı değildir.
İleti ve öncelik numaralarının kullanımına ilişkin bir örnek aşağıda verilmiştir.
Order sent by Order received by Order received by
Source IMP Dest. IMP HOST
---------- --------- ----
11,12P(1),13P(2),14 --> 13P(2),12P(1),14,11 --> 12P(1),13P(2),11,14
11,12P(1),13P(2),14 --> 13P(2),11,14,12P(1) --> 11,12P(1),13P(2),14
burada 13P(2), ileti #13, öncelik numarası (2) anlamına gelecek şekilde yorumlanır.
Yalnızca iki sınıf ileti olduğunu unutmayın: öncelikli ve önceliksiz. Öncelik numaraları, aynı siteden gelen birden fazla beklemede olan öncelikli iletinin hedefte sıralanmasına olanak tanır.
Eğer HOST’lar iletileri süreçlere ayırmak için bağlantı numaralarını kullanıyorsa, kısa iletilere keyfi olarak öncelik atamak bir hata olur. Bir dosya iletimi, son kısa iletinin öncelikli olacağı şekilde gerçekleştirilirse, dosya alıcı HOST’a gönderildiği sırayla girmeyebilir.
ACK Mekanizması
IMP’ler fiziksel kanallarını (telefon hatlarını) çiftler halinde simpleks iletişim yolları varmış gibi ele alır. Her IMPSYS, her bir tam çift yönlü kanal için bir gönderici ve bir alıcı modülüne sahiptir. Her modül, hattaki son paketin durumunu izlemek için kullanılan bir TEK/ÇİFT (ODD/EVEN) bitine sahiptir. Amaç, gönderici modülün, gönderilen paketin diğer uçta alındığını belirten bir paket alıcı tarafından alınıncaya kadar kanalı bloke etmesidir (yani bir onay).
Mevcut sistemde, onaylar ayrı IMP–IMP paketleridir. Yeni sistemde ise, tam çift yönlü bir kanalın ters yolunda karşı yönde akan bir paketin içinde tek bir bit olarak yer alırlar.
IMP’ler arasında gönderilen her paket, aşağıda gösterildiği gibi bir ACK biti ve bir OE biti taşır.
P A
O C
E K
+-------+-----+------------------------+-----+----------+
typical packet | | | | | |
| | | | | |
+-------+-----+------------------------+-----+----------+
Bazı terimlere ihtiyacımız var: POE paket OE biti olsun, SOE ve ROE ise sırasıyla gönderme-modülü OE biti ve alma-modülü OE biti olsun. A ve B olmak üzere iki IMP için, A ve B IMP’lerindeki iki gönderme-modülü OE bitini sırasıyla SOE/A ve SOE/B olarak ayırt ederiz.
Çalışma kuralları aşağıdaki gibidir:
Gönderici
- Eğer ACK ≠ SOE ise, hiçbir şey yapma.
- Aksi halde SOE ← ¬SOE (yani SOE bitini tersle) ve kanalı serbest bırak.
Alıcı
- Eğer POE = ROE ise, paket yinelenmiştir; bu yüzden at.
- Aksi halde ROE ← ¬ROE.
Bir paket gönderme modülü tarafından her gönderildiğinde, iki biti olan POE ve ACK şu şekilde ayarlanır:
- POE ← SOE
- ACK ← ROE
Bu mekanizma, gerçek paketlerin başlığına ACK bitlerini bindirerek, onay protokolünü gerçekleştirmek için gerçek trafiği kullanacak şekilde tasarlanmıştır. Karşı yönde iletim için bekleyen gerçek bir paket yoksa, ACK’i taşıyan ancak alıcı tarafça onaylanmayan sahte bir paket derlenir.
Bu mekanizmanın iki IMP arasındaki çalışmasına ilişkin bir örnek veriyoruz.
IMP A IMP B
----- -----
ROE | SOE ROE | SOE
| POE ACK |
| +-----------+ |
IMP A blocks send 1 | 0 (1)| 0 1 |-> 1 | 0 IMP B NOPs,
channel. | +-----------+ | flips ROE
| |
| POE ACK |
| +-----------+ |
IMP A frees send 0 | 1 <-| 0 0 |(2) 0 | 0 IMP B blocks
channel, | +-----------+ | channel for
flips SOE | | new traffic
| POE ACK |
IMP A blocks send | +-----------+ crashes|
channel | (3)| 1 0 |-> or gets
| +-----------+ lost |
| |
| POE ACK |
IMP A detects packet | +-----------+ |
duplicate (POE=ROE) 0 | 1 <-| 0 0 |(2) 0 | 0 IMP B
so does not change | +-----------+ | retransmits;
SOE bit. | | no ACK received
| POE ACK |
IMP A retransmits | +-----------+ | IMP B flips
packet (3) | (3)| 1 0 |-> 1 | 1 SOE, unblocks
| +-----------+ | channel, and
| | flips ROE
| POE ACK |
IMP A flips ROE, | +-----------+ |
flips SOE 1 | 0 <-| 1 1 |(4) |
| +-----------+ |
Aslında, her gönderme/alma modülünün 8 OE biti vardır; böylece her iki yönde de en fazla 8 paket beklemede olabilir.
İşlerin Gerçekte Nasıl Yürüdüğü
Gerçekte, tek bir gönderme modülü 8 sahte kanal üzerinden paket iletmeyi denemekten sorumludur. Her kanalın (bir OE bitine ek olarak) iki bitlik bir durumu vardır. Her kanal ya SERBEST (FREE) ya da KULLANIMDA (IN USE) durumundadır ve KULLANIMDA ise ESKİ (OLD) veya YENİ (NEW) bir paket gönderiyor olabilir.
start state F = free
| I = in use
V X = don't care
+-----+ +------+ N = new packet
| FX | --------------> | I, N | O = old packet
+-----+ +------+
^ |
| |
| |
| |
ACK | |
received | |
| V
| +------+
+-------------------| I, O |---+
+------+ |
^ | re-transmissions
+------+
IMP’ler arasında paketler, onaylanana kadar tekrar tekrar gönderilir. Ancak neyin gönderileceği seçimi aşağıdaki öncelik sırasına göre yapılır:
- Öncelikli paketler (HOST tarafından işaretlenen)
- Önceliksiz paketler
- Onaylanmamış paketler (I, O durumundaki kanallarda)
- Diğerleri
(1) ve (2) türündeki trafiğin ağır bir yük oluşturmasının, yeniden iletimlerin hiç gerçekleşmemesine yol açabileceği belirtilmiş ve W. Crowther, hatanın, sınıf (3)’teki eski paketlerin yeniden iletimini zorunlu kılan 125 ms’lik bir zaman aşımı ile düzeltileceğini söylemiştir.
Her paketin, POE–kanal ilişkilendirmesini tanımlamak için bir “sahte kanal” numarası ve (sahte kanallarla konumsal olarak ilişkilendirilmiş) 8 ACK biti taşıması gerektiğini unutmayın. Böylece tek bir paket aynı anda en fazla 8 paketi onaylayabilir.
[Bu RFC, çevrimiçi RFC arşivlerine girmek üzere makine tarafından okunabilir biçime Helene Morin, Via Genie tarafından, 12/99 tarihinde dönüştürülmüştür]