輸入/輸出太比特開關的rrgs－循環貪婪調度的製作方法

2023-10-05 08:00:34 2

專利名稱：輸入/輸出太比特開關的rrgs－循環貪婪調度的製作方法
技術領域：
本發明涉及應用於像電子和光介質上的太(1012)比特開關。特別是，本發明涉及一種循環貪婪調度算法。本發明包括調度方法和實現循環貪婪調度算法的太比特開關系統。
隨著對帶寬的持續增長的要求，相應地增加對太比特開關的需要，參見M.Beshai，和E.Miinter，「Multi-tera-bit/s switch basedon burst transfer and independent shared buffers」，ICC』95，pp.1724-1730，N.McKeown等，「The ting teraa packet switchcore，」IEEE Micro，vol.171，Jan.-Feb.1997，pp.26-33；W.D.Zhong，Y.Shimazu，M.Tsukuda，and K.Yukimatsu，「A modular Tbit/s TDM-WDMphotonic ATM switch using optical buffers」IEICE通訊學報vol.E77-B，no.2，February 1994，pp.190-196。帶電子控制的光開關磁芯(可看作是一個邏輯縱橫接線器)是高容量開關的一個有吸引力的選擇。在線速率為10Gb/s時，在40ns內必須處理64位元組單元/包.
本領域的技術人員面對的一個重要問題是如何作出快速的決定，將高效地使用光纜芯。這種情況下的開關設計可能包括輸入緩衝、輸出緩衝或者兩者都有。在具有輸出緩衝的開關中，輸出緩衝器要求存取速度大於開關的總吞吐量。作為一種選擇，採用頂出結構以便於降低所需輸出緩衝器的速度，這裡一定數量的單元被輸出緩衝器接受，其餘的被丟掉。如下的文章中提出光頂出開關，Zhong，Y.Shimazu，M.Tsukuda，and K.Yukimatsu，「A modular Tbit/s TDM-WDM photonic ATMswitchusing optical buffers」IEICE通訊學報vol.E77-B，no.2，February 1994，pp.190-196。由於每個輸出要求幾個光反向榕樹網絡和光緩衝器，因此開關複雜性高。
帶有輸入緩衝的開關以更為有效的方式使用緩衝器，而且需要的存儲器帶寬僅僅是線性速率的兩倍。在一個帶輸入緩衝的簡單方案中，所有的輸入要求傳輸位於它們各自隊列頂端的信息包。如果對同一輸出端需要兩個或多個的輸入端，則隨機地選取它們當中的一個。參見M.J.Karol，M.G.Hluchyj，和S.P.Morgan「Input vs.Output queuingon a space-division packet switch」IEEE通訊學報，vol.COM-35，no.12，December 1987，pp.1347-1356；其中表明在均勻業務量條件下輸入緩衝算法可使開關達到0.587的吞吐量。在非均勻業務量條件下效率進一步地降低。在其他的幾種調度方案中，除HOL(線頭)信息包外的信息包也參與輸出埠的競爭。參見R.Fan，M.Akiyama，和Y.Tanaka的「An input buffer-type ATM switching using schedulecomparison」日本電子與通訊，Part I，vol.74，no.11，1991，pp.17-25；S.Motoyama，D.W.Petr，和V.S.Frost的「Input-queuedswitch based on a scheduling algorithm」電子通訊，vol.31，no.14，July 1995，pp.1127-1128，和H.Obara的「Optimum architecture forinput queuing ATM switches」，電子通訊，vol.27，no.7，3月1991年，pp.555-557。在每個時隙裡，一個入端向幾個出端發送請求。在每個時隙僅4個請求的條件下，其效率可接近1。然而，此方案在高速情況下，多個請求/應答的調度在一個時隙內是不能被處理完成的(這裡一個時隙表示一個信息包傳輸時間)。而且，在帶熱點的非均勻業務量條件下，由於入端各自獨立地決定它們要請求哪一個出端，所以性能可能會降低。
如果開關控制器知道所有的輸入-輸出隊列的狀態，提高開關的性能是有可能的。此狀態信息能夠使開關控制器在一個時隙裡提高同時傳輸的數目。在SLIP規程中，出端各自獨立地向入端發送許可命令，這就導致一定的低效率。參見N.Mckeown，P.Varaiya，J.Walrand「Scheduling cells in an input-queued switch」電子通訊，vol.29，no.25，December 1993，pp.2174-2175。使用下文裡討論的算法，可在各輸入端之間實現更好的協調，參見D.Guo，Y.Yemini，Z.Zhang的「Scalable high-speed protocols for WDM optical starnetworks」IEEE INFOCOM′94。然而，這些算法都有一個缺點，就是它們都要求用許多時隙來做調度決定。
本發明的一個目的是要解決現有技術中的上述問題。特別是，本發明的一個目的是要提供一種方法，用兆太比特開關實現調度決定，此開關有效地使用光芯。本發明的更進一步目的是提供一種流水線結構，該結構實現循環式貪婪調度，同時在不提高內部速度的情況下提供良好的性能和滿足嚴格的時間要求。
為了實現上述目的，提供一種在對採用循環式貪婪調度規程的N×N縱橫接線器中確定一個時隙的方法，包括對應於N個出端的N個邏輯隊列，根據此規程，入端處於全部輸入-輸出隊列狀態，規程的輸出處於調度狀態，本方法包括以下步驟選擇相應於i＝(常數-k-1)mod N的入端，如果沒有多個入端，則停止，否則根據i＝(i+1)mod N以循環方式選擇下個入端；選擇出端j，使對(i，j)相應於集合C＝{(i，j)|從1到j至少有一信息包}，如果對(i，j)存在，從入端集合去掉i，並從出端集合中去掉j；將對(i，j)加到調度中，並重複這些步驟；如果對(i，j)不存在，則從入端集合去掉i，並重複這些步驟；本發明的另一方面是提供一種調度方法，其中在每個時隙裡，同時進行N個不同的調度，以確定N個未來的時隙，本方法包括以下步驟使入端能以循環的方式在特定的未來時隙得到調度；在未來的第k個時隙由入端i選擇出端；開始為未來的第k個時隙進行調度；確定下個入端(l+1)mod N，並把剩餘的出端送至下個入端，剩餘出端是指在第k個時隙可接收信息包的出端。
如果入端i是完成第k個時隙調度的最後一個入端，則此入端最好選擇一個出端(如果可行)，並將修改過的出端集合發送給下一入端；而且，如果入端l完成第k個時隙的調度，它不將出端集合發送給下個輸入。
最好是一個並未從以前的入端收到修改過的出端集合的入端開始新的調度。
本發明的另一方面是提供一種對奇數個入端的流水線式循環貪婪調度方法，其中完成第i個時隙的過程包括初始化k(0，l)＝k(1，l)＝...k(N-1，l)＝0，常數＝N+1，其中，如果k(i，l)＞0，是入端i在第i個時隙為其保留一個出端的時隙，il＝(常數-N-1)mod N表示在第1個時隙開始新的調度的入端，而且k(i，l)＝0意味著入端i在第1個時隙的動作受到阻止；設定Ol+N={0，1，，N-1)，k(il，l)＝l+N，k(i，l)＝k((i-1)modN，l-1)，0≤i≤N-1，而且i≠il；從集Ok(i，l)中以循環方式為入端i(0≤i≤N-1)選擇一個出端j，此入端i有信息包要發送，假定k(i，l)≠0並從Ok(i，l)中將j刪除；將選擇的出端存於入端i(0≤i≤N-1)的聯結存儲器位置k(i，l)mod N處，並將相應的接收輸入-輸出隊列的線頭(HOL)信息包移到單獨的發送輸入-輸出隊列；並在入端i(0≤i≤N-1)，而且i≠il-2 modN)，將集合Ok(i，l)轉送到下一入端(i+1)mod N；在入端i(0≤i≤N-1)和出端之間建立交叉連接，出端的地址是從入端i的聯結存儲器的位置(lmod(N+1))處讀取的；通過開關芯為每個入端i(0≤i≤N-1)將位於調度過的發送輸入-輸出隊列i頂端的剩餘信息包發送出去。
最好將多信道調度信息包括在循環式貪婪調度算法中，其中以先進先服務的方式存儲多信道信息包，而且比單信道隊列具有優先權，在第l個時隙採取的步驟進一步包括在入端i(0≤i≤N-1)選擇滿足j∈Ok(i，l)∩BMi條件的所有出端j，並在第k個時隙通過所選擇的出端將HOL多信道信息包傳送出去。如果Ok(i，l)∩BMi是空集，則服務單信道隊列，否則刪除從Ok(i，l)和BMi中選擇的出端；而且如果BMi是空集，則從多點隊列中刪除HOL多點信息包。
本發明的另一方面是對具有偶數個入端結構的流水線循環貪婪調度方法，其中，完成第l個時隙的過程包括初始化k(0，l)＝k(1，l)＝…k(N-1，l)＝0，常數＝N+1，其中，k(i，l)＞0是入端i在第l個時隙保存有輸出的時隙，il＝(常數-N-1)mod N表示在第1個時隙開始一個新的調度的入端，而且k(i，l)＝0意味著入端i在時隙l的動作被阻止；設置Ol+N={0，1，…，N-1)，k(il，l)＝l+N+1，k(mod(il+1)mod N，l)＝k(il，l-2)，而且k(i，l)＝k((i-1)mod N，l-1)，0≤i≤N-1並且i
(il，(il+1)modN)，同時l不等於ll在入端i(0≤i≤N-1)以循環方式從集合Ok(i，l)中選擇一個出端j，此入端i有信息包發送，假定k(i，l)≠0並且從Ok(i，l)中刪除j在入端i(0≤i≤N-1)將選擇的出端的地址存儲於與入端的聯結存儲器的位置k(i，l)mod(N+1)處，並從相關的接收輸入-輸出隊列的HOL信息包移到單獨的發送輸入-輸出隊列；將位於入端i(0≤i≤N-1，而且i＝(il-2)mod N)的集合Ok(i，l)移向下一個入端(i+1)mod N，其中入端(il-2)mod N在移向下個入端前延遲集合Ok((il-2)mod N，1)的一個時隙；在入端i(0≤i≤N-1)和出端之間建立交叉聯接，出端的地址是從入端i的聯結存儲器的位置(l mod(N+1))處讀取的；通過開關芯為每個入端i(0≤i≤N-1)將位於調度過的發送輸入-輸出隊列i頂端的剩餘信息包發送出去。
最好使多點調度信息包括在循環式貪婪調度算法中，其中以先進先服務的方式存儲多信道信息包，而且比單信道隊列具有優先權，而在第i個時隙採取的步驟進一步包括在入端i(0≤i≤N-1)選擇滿足j∈Ok(i，l)∩BMi條件的j，並在第k個時隙通過所選擇的出端將HOL多信道信息包傳送出去。如果Ok(i，l)∩BMl是空集，則服務單信道隊列，否則除了被選擇的出端以外，從Ok(i，l)和BMl中被除去；而且如果BMi是空集，則將HOL多信道信息包從多信道隊列中刪除掉。
本發明的另一方面是用於調度N×N縱橫接線器的一個N級流水線系統，其中級i與入端i相關，所述級i在未來時隙調度向輸出的傳輸，所述未來時隙遊歷所有各級，其中與入端對應的流水線級同時進行調度，以便於沒有兩個入端在同一時間選擇相同的未來時隙，選中的輸出時隙是基於循環式的，其中，當某出端被某級選中後，就將此出端從可選的自由出埠中移去，以便於在一個時隙中流水線級不再選已經被選擇的出端。
通過參考附圖詳細地描述最佳實施例，本發明的上述目的和優點就會變得更清楚，其中

圖1示出開關控制器(N＝5)的最佳實施例時序圖；圖2示出開關控制器(N＝4)的最佳實施例時序圖；圖3示出實現一個N×N縱橫接線器的控制；圖4示出根據分析和仿真結果實現RRGS，RGS，HOL，SLIP，和I-TDMA的平均信息包延遲的比較；圖5A、B示出根據仿真結果在固定業務量(A)0.8和(B)0.9條件下TDMA，SLIP，RGS和RRGS的信息包延遲的互補分布函數；圖6A-D示出在非均勻業務量條件下對應於RRGS，RGS，SLIP和I-TDMA的四組隊列(A)G1(B)G2(C)G3和(D)整體的平均信息包延遲。
按照本發明流水線結構實現「循環貪婪調度」(RRGS)。這是對隨機貪婪調度(RGS)的修改和改進，參見R.Chipalkatti，Z.Zhang，和A.S.Acampora的「Protocols for optical star-coupler network usingWDMperformance and complexity study」，IEEE雜誌通訊選集，vol.11，no.4，May 1993，pp.579-589；和D.Guo，Y.Yemini，Z.Zhang的「Scalable high-speed protocols for WDM optical star networks」，IEEE INFOCOM』94。本發明的規程能實現嚴格的時序要求而不提高內部的速度，同時保持了RGS的良好的性能。參見D.Guo，Y.Yemini，Z.Zhang的「Scalable high-speed protocols for WDM optical star networks」，IEEE INFOCOM』94。它幾乎達到了100％的使用率，並同樣很好地處理非均勻業務量的情況。1.循環貪婪調度(RRGS)現在詳細地描述最佳實施例。本發明中使用的規程稱為RRGS規程。考慮一個N×N縱橫接線器，其中，每個入端i(i∈{0，1，...，N-1}有N個邏輯隊列，相應於N個出端中的每一個。由所述接線器接收到的所有信息包都是固定長度的信元。RRGS規程的入端是全部輸入-輸出隊列的狀態。這樣的入端可用如下的集合C所描述C＝{(i，j)/入端i至少有一個信息包要在出端j輸出}。
規程的輸出是一個使入端與出端相聯繫的調度。這樣的集合S可描述如下S＝{(i，j)/信息包將被從入端i送到出端j}。
對於一個熟練技術人員來講將會清楚，在每個時隙內，一個入端只能傳送一個信息包，而且一個出端只能接收一個信息包。在這種條件下，任意第k個時隙的調度可按如下步驟確定步驟1)Ik＝{0，1，...，N-1}是所有入端集合，Ok＝{0，1，...，N-1}是所有出端集合。選擇i＝(常數-k-1)mod N。這樣選擇入端開始調度將使實現得以簡化。
步驟2)如果Ik是空集，則停止。否則，根據i＝(i+1)mod N以循環方式選擇下一入端i。
步驟3)以循環方式從Ok中選取出端j，使(i，j)0 Ck。如果不存在這樣的出端，則從Ik中除去i，進到步驟2。
步驟4)從Ik中去掉入端i，並從Ok中去掉出端j，把(i，j)加到Sk中，進到步驟2。
上述規程明顯地是對傳統的RGS的改進。參見D.Guo，Y.Yemini，Z.Zhang的「Scalable high-speed protocols for WDM optical starnetworks」，IEEE INFOCOM』94。亦參見R.Chipalkatti，Z.Zhang，和A.S.Acampora的「Protocols for optical star-coupler network using WDMperformance and complexity study」，IEEE雜誌通訊選集，vol.11，no.4，May 1993，pp.579-589，其中講述了DAS算法。在傳統的RGS中，入端和與之配對的出端都是隨機地被選取的。然而，這樣的一個隨機的選取方案實現起來實際上是困難的。要說明的是，在每個時隙，N個信息包可從N個入端轉送到N個出端。
在RRGS中對給定時隙的調度過程包括N步。在給定時隙(將來)的每步，一個入端從餘下的出端中選擇其一用於在所述時隙傳輸。每步包括從入端模塊(IM)到循環(RR)判優程序、RR選擇的請求、和從RR判優程序來的對IM的確認。入端選擇出端的循環次序在每個時隙周期性地移位，以便保證所有入端平等地訪問。2.有奇數個入端的流水線化的RRGS在高的連接速度(如10Gb/s)下，在一個時隙內(假定信息包大小是64位元組時為40ns)不能完成N步。隨著日益增長的連接速度，用傳統的技術在一個時隙內僅僅能完成一步。為了克服這個問題，本發明採用流水線逼近方法，其中，在每個時隙，為N個不同的時隙(將來的)同時進行N個不同的調度。對特定的調度的每一步僅涉及一個入端。在任何給定的時隙裡，其它的入端同時對其它不同的未來時隙進行調度步驟。
定義當所有的N個步驟都完成時，也就是說，當所有的入端在Tk期間都有機會選擇(順序地或相反)一個出端用來傳輸時，我們稱對未來時隙Tk的調度完成了。
雖然完成給定調度的N步需要N個時隙，採用流水線逼近方法通過並行地計算N個調度，就能夠在一個時隙內完成N個不同調度的N步。但是，這等效於在每個時隙完成一個調度。在RRGS中，對入端而言以循環方式可對未來特定時隙進行調度。對於開始對未來的第k個時隙進行調度的入端i，以循環(RR)的方式選擇出端，並傳遞到下個入端(i+1)mod N，則集合Ok指示在第k個時隙期間仍處於空閒可接收信息包的輸出埠。任何由前面入端(i-1)mod N接收的入端i設定對第k個時隙適用的出端集合Ok，如果可能的話從此集合選擇一個出端，並且如果入端i沒有完成對第k個時隙Tk的調度，就將修改過的集合Ok傳遞給下個入端(i+1)mod N。完成第k個時隙調度的入端i不應該將修改過的集合Ok轉到下個入端(i+1)mod N。這樣，沒有收到當前時隙的集合Ok的入端(i+1)mod N將在下個時隙開始(為新時隙)進行新的調度。RRGS的步驟1意味著在N個時隙裡一個入端阻止向下傳遞集合Ok一次。不向下傳遞集合Ok的入端應是為第k個時隙選擇出端的最後一個入端。
命題1如果入端(常數-k)mod N在第(k-1)個時隙裡阻止向下傳遞集合Ok，而且入端數目N是奇數，則入端(常數-k)mod N完成第k個時隙的調度。
證明上述命題意味著·在每個時隙裡，所有N個入端都有機會為一個未來時隙調度傳輸。
·在每一個時隙，一個入端僅能為一個未來時隙調度傳輸。
·在每一個時隙，可使一個出端被調度成僅能從一個入端接收傳輸。
在第(k-1)個時隙，固定入端i＝(常數-k)mod N，此入端阻止向下傳遞集合Ok。在這種情況下，前面N-1個入端的每個入端在第k個時隙內預定一個出端後必須將集合Ok向下傳送。要說明的是在第(k-1-j)個時隙，入端(i+j)mod N不向下個入端轉送集合Oi。另外，入端(i-j)mod N為第k個時隙預定一個出端。如果(1≤j≤(N-1))i-j≠i+j mod N
(1≤j≤(N-1))2.j≠0 mod N
N是奇數的話，則這樣的調度是可行的。
由於入端I在第(k-N-1)個時隙不轉送集合Ok-N，所以在第(k-N)個時隙為第k個時隙的調度是從入端(i+1)mod N開始的。
圖1示出一個5×5的縱橫接線器實施例的時序圖。此圖顯示入端和用於它們選擇其出端的時隙之間的關係。例如，在時隙T5，入端I正在調度或選擇一個在時隙T10傳輸的出端，同時，I3正在為T9調度等等。在下個時隙T6，I1正在為T8調度等等。黑粗垂直線表示前面的入端完成了一個調度，而且下個入端將開始一個新的調度。如果入端是為相關的時隙選擇出端的最後一個入端，則此入端就不向下一入端轉送集合O。由於這種條件每N(＝5)個時隙只發生一次，通過模N計數器，入端作出不向下轉送集合O的決定。
最後，在第個時隙(例如當前時隙)，由RRGS採取動作。Ok表示適合於第k個時隙的出端的集合。設k(i，l)＞0表示入端i在第l個時隙預留出端的時隙。而且il(常數-N-1)mod N表示在第1個時隙開始一個新調度的入端。並且，K(i，l)＝0意味著在時隙1入端i的動作受到阻止。調度程序需要正確的初始化。初始化的周期需要持續N個時隙。假定初始化過程在第一個時隙T1開始。通過設定k(0，l)＝k(1，l)＝…＝k(N-1，l)＝0，常數＝N+1，使初始化過程開始。也就是說，在頭N個時隙所有入端的動作都受到阻止，除非隨後調整。還假定所有信息包以邏輯上分開的隊列形式在入端排隊，此形式叫做輸入-輸出隊列，每個輸出埠的一個隊列防止HOL阻塞。另外，還提供接收輸入-輸出隊列和傳送輸入-輸出隊列。
·Ol+N＝{0，1，，N-1}·k((il，l)＝1+N，而且，k(i-l)＝k((i-1)mod N，l-1)，0≤i≤N-1，且i≠il·入端i(0≤i≤N-1)以RR方式從集合Ok(i，l)中選擇出端j，入端i有信息包要發送，給出k(i，l)≠0。[入端i(0≤i≤N-1，且i≠il，)，在前面時隙從入端(i-1)mod N接收Ok(i，l))。出端j從Ok(i，l)中被排除。
·入端i(0≤i≤N-1)將所選擇的出端地址存於該入端的聯接存儲器的k(i，L)mod N處。將來自相應的接收輸入輸出隊列的行信息包頭移到單獨的發送輸入-輸出隊列。
·入端i(0≤i≤N-1，而且i≠(il-2)mod N)傳送集合Ok(i，l)到下個入端(i+1)mod N。要說明的是僅N比特的信息需要被傳遞。
·在入端i(0≤i≤N-1)和出端之間建立一個交叉聯接，並從入端i的聯接存儲器的位置(l mod N)處讀取出端的地址。
·對每個入端i(0≤i≤N-1)，被調度的傳輸輸入-輸出隊列的HOL信息包通過開關磁芯被發送。3.有偶數個入端的流水線化的RRGS在有奇數個入端的方案中，如果入端是為未來時隙選擇出端的最後一個入端，每個入端阻止調整過的集合Ok傳送到下個入端(鄰端)，這樣就完成了該時隙的調度。這種算法(為奇數N開發)的直接應用是導致某些入端用於調度不止一個未來時隙，而其它入端根本不參與調度。於是，為了控制有偶數個入端的開關，就要調整流水線技術。
命題1的證明推斷出延遲控制信息而不是阻塞控制信息將意味著偶數個輸入端。對於偶數入端的情況，每個入端在N個時隙裡阻止將集合Ol到下個入端一次，而在下個時隙裡入端從前個時隙獲得的延遲一個時隙的集Ol傳遞下去。當入端傳送延遲的集Ol時，它將不傳遞當前的集Ok。因此，入端i應是為第k個時隙選擇出端的最後一個入端。
命題2如果入端(常數-k)mod N在第(k-2)個時隙延遲集Ol(並在第(k-1)個時隙傳送它)，而且入端數目N是偶數，那麼入端(常數-k)mod N完成第k個時隙的調度。
證明固定入端(常數-k)mod N，它在第(k-2)個時隙延遲集合Ol，並在第(k-1)個時隙傳送被延遲的集合Ol而不是集合Ok。這樣，在第(k-1-j)個時隙，入端(i+j-1)mod N延遲集合Om，入端(i+j)mod N傳送被延遲的集合On，在第(k-1-j)個時隙，入端(i-j)mod N為第k個時隙預留，並向下傳遞集Ok其中Ok給出i-j≠i+j mod N，而且i-j≠i+j-1mod N，這裡的N滿足0≤j≤N/2且N為偶數。在第(k-1-N/2)個時隙期間，入端(i-N/2)mod N存儲Ok，導致沒有入端可預留給第k個時隙。
在第(k-2-N/2)個時隙，入端(i-N/2)為第k個時隙預留。在第(k-1-j)個時隙(N/2+2≤j≤N)，入端(i-j+1)mod N為第k個時隙預留，並傳送Ok，其中Ok給出i-j+1≠i+j mod N且i-j+1≠i+j-1 mod N，這裡的N為偶數。
因此，第k個時隙的調度遊歷整個流水線，在完成前不被用戶i中斷。此調度在第(k-N-1)個時隙由用戶(i+1)mod N啟動，因為入端i在第(k-N-2)個時隙延遲控制信息。
圖2示出一個4×4縱橫接線器實施例的時序圖，它示出偶數個入端的情況。長方形陰影表示控制信息O的延遲。黑粗垂線表示前面的入端完成調度，而下個入端將開始新的調度。
再者，對於入端為偶數的情況，在第1個時隙RRGS採取的動作是確定的。Ok表示第k個時隙可獲得的出端的集合。設k(i，l)＞0表示入端i在第1個時隙為入端i預留出端的時隙，而且i1-(常數-N-1-l)modN表示在第1個時隙開始新調度的入端。設定K(i，l)＝0意味著在時隙1入端i的動作受到阻止。調度程序需要正確的初始化。初始化周期持續N個時隙。假定初始化過程在第一個時隙T1開始。通過設置k(0，l)＝k(1，l)＝…＝k(N-1，l)＝0，常數＝N+2，開始初始化過程。也就是說，在頭N個時隙所有入端的動作都受到阻止，除非隨後調整。
O1+N+j＝{0，1，，N-1}k(il，l)＝1+N+1，k(mod((il+1)modN，l)＝k(il，l-2)，且k(i，l)＝k((i-1)mod N，l-1)0≤i≤N-1，且i
(il，(il+1)mod N)。
入端i(0≤i≤N-1)以RR方式從集合Ok(i，l)中選擇出端j，入端i有信息包要發送，給出k(i，l)≠0(入端i(0≤i≤N-1，i≠il，)，在前面時隙從入端(i-1)mod N接收集Ok(i，l))。出端j從Ok(i，l)中被排除。
入端i(0≤i≤N-1)將所選擇的出端的地址存於入端的聯接存儲器位於k(i，l)mod(N+1)處。將來自於相應接收輸入一輸出隊列的HOL信息包移到獨立的發送輸入-輸出隊列。
入端i(0≤i≤N-1，且i≠(il-2)mod N)傳送集合Ok(i，l)到下個入端(i+1)mod N。入端((il-2)mod N在傳遞集合Ok((il-2)mod N，l)之前將它延遲一個時隙。
在入端i(0≤i≤N-1)和出端4之間建立一個交叉聯接，出端4的地址是從入端i的聯接存儲器位置(l mod(N+1))處讀取的。
對每個入端i(0≤i≤N-1)，被在調度的傳輸輸入一輸出隊列頭部的保留信息包通過開關磁芯被發送。
4.多信道調度本發明的另一方面是包括多信道功能。多信道信息包存儲在獨立的隊列裡，其是以先入先服務的方式(FCFS方式)服務。每個隊列有一個多信道位表(BM)，它指明它的HOL信息包的目的地。在最簡單的情形，多信道信息包將比單信道信息包有優先權。在第i個時隙進行的附加多信道操作如下·入端i(0≤i≤N-1)選擇所有的出端j(例如j∈Ok(i，l)∩BMi)。HOL多信道信息包在第k個時隙將被傳送到所選的出端。
·如果Ok(i，l)∩BMi是空集，單信道隊列得到服務。否則，從Ok(i，l)和BMi中排除掉被選中的出端以外的出端。
.如果BMi是空的，就從多信道隊列中刪除HOL多信道信息包。5.開關控制器的實現圖3示出一個N×N光學縱橫接線器所用的控制器。每個入端需要一個輸入模塊(3.11，3.21，3.31，...，3.N1)，一個RR判定器和流水線式控制器(3.12，3.22，3.32，...3.N2)，和一個連接存儲器(3.13，3.23，3.33，...，3.N3)。輸入模塊(IM)以邏輯上分離的接收隊列方式存儲所接收的信息包，每個隊列確定於一特定的輸出。IM向與其相關的RR判定器發送請求。RR判定器選擇一個在未來時隙為空閒的出端，並將有關所做的這種選擇通知相應的入端和流水線式控制器。要說明的是對流水線的初始化過程確保在任何給定的時隙，沒有兩個判定器選擇相同的未來時隙用於調度傳輸。輸入模塊把成功的信息包存儲到獨立的傳輸輸入-輸出隊列。RR判定器也將其調度決定寫入與之相關的聯接存儲器的特定存儲位置。存儲器中的位置由信息包調度用的時隙來確定。流水線控制器通知下個入端的RR判定器，所有還沒有被某特定時隙預留的出端；更精確地講，控制器禁止對這些預留的出端訪問。如果某些入端不轉發控制信息，則它的流水線控制器允許下個入端的RR判定器能夠為未來時隙選擇任何出端。
根據寫入聯接存儲器中的調度，通過開關磁芯將來自輸入模塊的信息包轉送到輸出端模塊。6.性能比較在這部分，把iRRGS與有相似複雜性的其它規程進行比較。複雜性是以規程完成一個調度所需的時間來測定的。比較HOL、I-TDMA、SLIP、RGS和RRGS規程。參見K.Bogineni，K.M.Sivilingam，和P.W.Dowd的「Low-complexity multiple access protocols for wavelength-divisionmultiplexed photonic networks」IEEE雜誌通信選集，vol.11，no.4，May 1993，pp.590-604；D.Guo，Y.Yemin，Z.Zhang的「Scalable high-speed protocols forWDM optical star networks」IEEE INFOCOM』94；M.J.Karol，M.G.Hluchyj，和S.P.Morgan的「Input vs.output queuing on a space-division packet switch」IEEE通信文集，vol.COM-35，no.12，December 1987，pp.1347-1356；和N.McKeown，P.Varaiya，J.Walrand的「Scheduling cells in an input-queuedswitch」電子通訊，vol.29，no.25，December 1993，pp.2174-2175。
對於入端排隊開關的最簡單的規程就是線頭(HOL)規程，參見M.J.Karol，M.G.Hluchyj，和S.P.Morgan的「Input vs.output queuing on aspace-division packet switch」IEEE通信文集，vol.COM-35，no.12，December1987，pp.1347-1356。每個入端向合適的出端發送請求，要求傳輸HOL信息包。被請求的出端以循環方式向其中一個入端發出允許。在下個時隙，被允許的入端將信息包發送到相應的出端。
在間插的TDMA(I-TDMA)中，以固定的方式將出端指定給入端，參見K.Bogineni，K.M.Sivilingam，和P.W.Dowd的「Low-complexity multipleaccess protocols for wavelength-division multiplexed photonic networks」IEEE雜誌通信選集，vol.11，no.4，May 1993，pp.590-604。時間劃分為多個幀，傳輸調度被預先確定在幀的每個時隙中。依據它們的目的地將信息包存儲在分立的隊列中，並在預定的時隙發送。
參見N.McKeown，P.Varaiya，J.Walrand的「Scheduling cells in an input-queued switch」電子通訊，vol.29，no.25，December 1993，pp.2174-2175，該文提出採用slip(SLIP)迭代循環匹配。每個入端向所有的出端發送請求，入端有信息包發送給出端。被請求的出端以循環的方式向請求入端之一發出允許。接收到多個允許的入端以循環方式選擇其中一個被允許的出端。從上個被選中的入端之後的位置處開始每個以循環方式進行的選擇。
隨機貪婪調度(RGS)同RRGS是相似的，除了前者用隨機選擇方式代替循環選擇方式，參見D.Guo，Y.Yemini，Z.Zhang的「Scalable high-speedprotocols for WDM optical star networks」IEEE INFOCOM』94。控制器隨機地選擇入端隊列，並隨機地同未被配對的出端進行匹配。在高速情況下，不能在一個時隙內完成RGS；然而，我們評估它的性能，以便探究用循環方式選擇代替隨機方式選擇所產生的影響。
圖4分別為HOL、I-TDMA、SLIP、RGS和RRGS繪製了給定業務量的平均信息包延遲曲線。獲得的分析性能結果和模擬結果吻合的很好。
圖5示出在固定給定業務量條件下分別對應I-TDMA、SLIP、RGS、RRGS的信息包延遲互補分布函數。繪製的曲線是利用模擬的結果得到的。對於大多數業務量負荷下，RRGS的性能明顯地超過I-TDMA和SLIP的性能。
圖6示出對四個不同負載G1、G2、G3和G4的話務模型非均勻業務量的協議性能。7.結論本發明提出一種並行循環方式調度程序，該程序用於快速入端緩衝的信息包開關。本發明的RRGS規程與複雜程度相似的其它規程相比具有更短的平均信息包延遲。信息包延遲分布沒有嚴重的尾端。在非均勻業務量的條件下，與其它規程的延遲比較，負荷較輕的信息包延遲較長，但負荷較重的信息包具有明顯短的延遲。
通過前面公開和教導的內容，有關本發明的其他改進和變形對本領域的技術人員來說都是顯而易見的。因此，雖然這裡只是具體地描述本發明的一些實施例，顯然在不脫離本發明的精神和範圍的條件下，可以進行許多變形。
權利要求
1.一種用於在循環貪婪調度規程的N×N縱橫接線器中確定時隙的方法，所述規程在每個入端包括N個邏輯隊列，對應於N個輸出埠，所述規程的入端處於全輸入-輸出隊列的狀態，所述規程的出端處於調度狀態，該方法包括a)對應於i＝(常數-k-1)mod N選擇入端；b)如果沒有多個入端，則停止，否則以循環方式對應於i＝(i+1)mod N選取下個入端；c)如果對(i，j)存在，選取出端j使對(i，j)屬於集合C＝{(i，j)|從1到j至少有一個信息包}；d)如果在步驟c)中對(i，j)不存在，將i從入端集中去掉，並進到步驟b)；e)將i和j分別從入端集合和出端集合中去掉；f)將對(i，j)加到調度中，並進到步驟b)。
2.一種調度方法，其中在每個時隙，對N個未來時隙同時進行N個不同的調度，該方法包括a)使入端可以以循環方式在特定的未來時隙得到調度；b)由入端i在未來的第k個時隙選擇出端；c)開始為未來的第k個時隙進行調度；d)確定下個入端(i+1)mod N，並把在第k個時隙期間可以接收信息包的出端發送到下個入端。
3.如權利要求2所述的方法，其中如果入端i沒有完成第k個時隙的調度，選擇一個出端，並將修改過的出端集合發送到下個入端；如果入端i完成第k個時隙的調度，則此入端就不將出端集合發送到下個入端。
4.如權利要求3所述的方法，其中一個並未從上個入端接收到修改過的出端集合的入端開始一個新的調度。
5.一種用於奇數個入端的流水線循環貪婪調度的方法，其中完成第i個時隙的過程包括e)初始化k(0，l)＝k(1，l)＝…k(N-1，l)＝0，常數＝N+1，其中，k(i，l)＞0是入端i在第1個時隙預留有出端的時隙，il＝(常數-N-1)mod N表示在第1個時隙開始新的調度的入端，而且k(i，l)＝0意味著入端i在時隙l的動作受到阻止；f)設置Ol+N＝{0，1，，N-1)，k(il，l)＝l+N，k(i，l)＝k((i-1)mod N，l-1)其中0≤i≤N-1，而且i≠il；g)在入端i，0≤i≤N-1，以循環方式從集合Ok(i，l)中選擇一個出端j，此入端有信息包要發送，假定k(i，l)≠0，並從集合Ok(i，l)中排除j；h)在入端i，O≤i≤N-1，將所選擇的出端地址存於入端i的聯結存儲器的位置k(i，l)mod N處，並將來自相應的接收輸入一輸出隊列的信息包線頭(HOL)移到單獨的發送輸入-輸出隊列；i)將位於入端i，0≤i≤N-1，而且i≠(il-2)mod N的集合Ok(i，l)傳遞到下個入端(i+1)mod N；j)在入端i，0≤i≤N-1，和出端間建立交叉聯接，所述出端的地址是從入端i的聯接存儲器的位置(l mod(N+1))處讀取的；k)對每個入端i，0≤i≤N-1，通過開關磁芯將位於調度的發送輸入-輸出隊列i頭的預留的信息包發送出去，
6.一種用於偶數個入端的流水線循環貪婪調度的方法，其中為第i個時隙調度的過程包括1)初始化k(0，1)＝k(1，1)＝…k(N-1，1)＝0，常數＝N+1，其中，k(i，l)＞0是入端i在第1個時隙預留有出端的時隙，il＝(常數-N-1)mod N表示在第1個時隙開始新的調度的入端，而且k(i，l)＝0意味著入端i在時隙l的動作受到阻止m)設置Ol+N=(0，1，，N-1)，k(il，l)＝1+N+1，k(mod(il+1)mod N，l)＝k(il，l-2)，而且k(i，l)＝k((i-1)mod N，l-1) 其中0≤i≤N-1，而且(il+1)mod N)，而且i
{(il，(il+1)mod N}；n)在入端i，0≤i≤N-1，以循環方式從集合Ok(i，l)中選擇一個出端j，該入端有信息包要發送，假定k(i，l)≠0，並從集合Ok(i，l)中排除j；o)在入端i，0≤i≤N-1，將所選擇的出端地址存於它的聯接存儲器的位置k(i，l)mod(N+1)處，並將來自於相應的接收輸入-輸出隊列的OHL信息包移到單獨的發送輸入-輸出隊列；p)在入端i，0≤i≤N-1，而且i＝(il-2)mod N將集合Ok(i，l)傳遞到下個入端(i+1)mod N，其中，入端(il-2)mod N在傳遞集合Ok(il-2)mod N，1)之前將其延遲一個時隙；q)在入端i，0≤i≤N-1，和出端間建立交叉聯接，所述出端的地址是從入端i的聯接存儲器的位置(l mod(N+1))處讀取的；r)對每個入端i，0≤i≤N-1，通過開關磁芯將位於調度的發送輸入-輸出隊列頭的預留的信息包發送出去。
7.如權利要求5所述的方法，其中在循環貪婪算法中包括多信道調整度，其中多信道信息包以先進先服務的方式被存儲，而且多信道隊列比單信道隊列有優先權，在第i個時隙的步驟進一步包括s)在入端i，0≤i≤N-1，選擇所有的出端j，使j∈Ok(i，l)∩BMi，在第k個時隙將HOL多點信息包傳送到所選的出端。t)如果Ok(i，l)∩BMi是空集，單信道隊列得到服務，否則，從Ok(i，l)和BMi中排除掉被選中的出端以外的出端；u)如果BMi是空的，就從多信道隊列中刪除掉HOL多信道信息包。
8.根據權利要求6所述的方法，其中在循環貪婪調度算法中包括多信道調度，其中多信道信息包以先進先服務的方式被存儲，且比單信道隊列有優先權，在第i個時隙的步驟進一步包括v)在入端i，0≤i≤N-1，選擇所有的出端j，使滿足j∈Ok(i，l)∩BMi。w)在第k個時隙將HOL多信道信息包傳送到所選的出端。x)如果Ok(i，l)∩BMi是空集，則服務單信道隊列，否則，從Ok(i，l)和BMi中排除掉被選中的出端以外的出端。y)如果BMi是空的，就從多信道隊列中刪除掉HOL多信道信息包。
9.一種用於調度N×N縱橫接線器的N級流水線系統，這裡級i與入端i相關，在未來時隙向出端傳輸所述級i調度，所述未來時隙脈衝通過整個全部級，其中與所有入端對應的流水線級同時進行調度，以便沒有兩個入端在同一時間選擇相同的未來時隙，選中的時隙是基於循環方式的，其中當一個出端被一級選中後，就將此出端從可選的自由出埠中移去，以便於時隙中流水線級不再選已經被入端在一個時隙選擇的出端。
全文摘要
本發明的循環貪婪調度(RRGS)採用流水線技術可在太比特吞吐量下實現優化調度。流水線逼近法避免對開關結構內部速度的需求而達到高使用率。採用循環貪婪調度規程的N×N縱橫接線器中確定時隙的方法包括:相對於i=(常數－k－l)modN選擇入端,如果對(i,j)存在,選擇出端j,使對(i,j)屬於集合C={(i,j)丨從1到j至少有一個信息包}。如果對(i,j)不存在,將入端i從入端集合中去掉,並重複所述步驟;從入端集合去掉i,並從出端集合去掉j;把對(i,j)加到調度並重複所述步驟。
文檔編號H04Q3/00GK1264226SQ9911082
公開日2000年8月23日 申請日期1999年7月22日 優先權日1998年12月8日
發明者拉馬穆爾蒂·戈帕拉克裡希南, 範瑞學, 斯米利亞尼奇·亞歷山德拉 申請人:日本電氣株式會社