IM-OM matching packet dispatching scheme for MSM Clos-network

• Autorzy: Kleban J. , Węclewski S.

Warianty tytułu

PL

Planowanie przepływu pakietów w polach Closa typu MSM na zasadzie dopasowania modułów IM-OM

• Języki publikacji: PL

Abstrakty

PL

Stosowane obecnie w routerach/przełącznikach rozwiązania nie pozwalają˛ na osiągniecie bardzo dużych przepustowości charakterystycznych dla węzłów sieciowych następnej generacji. Sytuacja ta implikuje bardzo intensywne poszukiwania nowych, skalowalnych architektur dla tego typu urządzeń´. Ze względu na ograniczenia technologiczne konstruowanie węzłów sieciowych o przepustowościach sięgających Tb/s lub Pb/s jest ogromnym wyzwaniem. W pakietowych węzłach sieciowych następnej generacji coraz częściej zakłada się możliwość wykorzystania wielosekcyjnych pól komutacyjnychClosa ze względu na możliwość łatwej rozbudowy i zwiększania pojemności. Wyróżnia się pola Closa z buforowaniem w pierwszej i trzeciej sekcji - MSM (ang. Memory-Space-Memory) i bez buforowania - SSS (ang. Space-Space-Space). Jednym z bardzo istotnych elementów architektury pola komutacyjnego routera są bufory wykorzystywane do rozwiązywania konfliktów wynikających z kierowania pakietów do tych samych wyjść. Bufory mogą˛ być´ umieszczone po stronie wejściowej, wyjściowej lub wewnątrz pola komutacyjnego. Szeroko dyskutowane w literaturze rozwiązanie z buforowaniem wejsciowym zakłada wykorzystanie tzw. wirtualnych kolejek wyjściowych VOQ (ang. Virtual Output Queuing). W tym przypadku bufor wejściowy w każdym porcie wejściowym jest dzielony na k równoległych kolejek, z których każda przechowuje pakiety kierowane do danego wyjścia pola komutacyjnego. W tym przypadku istnieje potrzeba zastosowania dobrego algorytmu planowania przepływu pakietów przez pole komutacyjne, zapewniającego osiągniecie dużej przepływności i małego opóźnienia. Układy planowania rozstrzygające spory o dostęp do zadanych wyjść´ nazywane są˛ arbitrami. Stosowane są˛ układy arbitrażowe centralne lub rozproszone. Różne algorytmy planowania przepływu pakietów były rozpatrywane w literaturze, większość z nich zapewnia uzyskanie 100% przepustowości dla ruchu równomiernego oraz ograniczona˛ przepustowość´ dla ruchów o rozkładzie nierównomiernym. W wielu obecnie stosowanych algorytmach planowania przypływu pakietów wykorzystywany jest efekt desynchronizacji wskaźników, a proces podejmowania decyzji o tym, która komórka z wejścia zostanie przesłana do wyjścia składa się co najmniej z trzech etapów, w których przesyłane są˛ sygnały żądania, potwierdzenia oraz akceptacji. Przy użyciu obecnie dostępnej technologii SERDES nie jest możliwe zrealizowanie w pojedynczej szczelinie czasowej arbitrażu opartego na przesyłaniu sygnałów żądanie-potwierdzenie-akceptacja, które musza˛ być parokrotnie przesłane przez złącza szeregowe. Istnieje zatem potrzeba poszukiwania algorytmów, które minimalizowałyby liczbę interakcji miedzy poszczególnymi elementami pola komutacyjnego.

EN

Current packet dispatching algorithms for next generation network nodes (switches/routers), in the majority of cases, involve the request-grant-accept handshaking scheme with many iterations and the effect of desynchronization of arbitration pointers. For high-performance switches and routers the Clos switching fabric is very attractive because of its modular architecture and scalability. It is almost impossible to implement the algorithms with multiple phase iterations in the three-stage Clos-network environment with currently available technologies, as the arbitration signals need to pass through the SERDES links several times, and the delay is too long. A great many packet dispatching schemes for three-stage buffered and bufferless Clos switching fabrics were proposed in the literature. Some of them provide high throughput under uniform, others under nonuniform traffic distribution. In this paper the new packet dispatching scheme, called IM-OM Matching (IOM), is proposed and evaluated. We have eliminated the handshaking process and iterations, but it is necessary to use the central arbiter instead. The IOM scheme may be implemented in the MSM as well as in the modified MSM Clos-network switches. We show via simulation that the proposed scheme delivers very good performance in terms of throughput, cell delay and input buffers size under different traffic distribution patterns.

Słowa kluczowe

EN

Clos-network; dispatching algorithm; packet switching; packet scheduling

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2007
• Tom: Vol. 19, No. 3
• Strony: 159--173
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Kleban J.

autor

Węclewski S.

• Chair of Telecommunication and Computer Networks Faculty of Electronics and Telecommunications Poznan University of Technology ul. Polanka 3, 60-965 Poznań, Poland,

Bibliografia

• [1] Chao H.J., Lam C.H., Oki E.: Broadband Packet Switching Technologies: A Practical Guide to ATM Switches and IP Routers. Willey, New York, 2001.
• [2] Yoshigoe K., Christensen K.J.: An evolution to crossbar switches with virtual ouptut queuing and buffered cross points’. IEEE Network, vol. 17, no. 5, 2003, pp. 48-56.
• [3] Oki E., Rojas-Cessa R., Chao H.J.: A pipeline-based approach formaximal-sizedmatching scheduling in input-buffered switches. IEEE Communications Letters, vol. 5, no. 6, 2001, pp. 263-265.
• [4] Oki E., Jing Z., Rojas-Cessa R., Chao H.J.: Concurrent Round-Robin-Based Dispatching Schemes for Clos-Network Switches. IEEE/ACM Trans. on Networking, vol. 10, no. 6, 2002, pp. 830-844.
• [5] Rojas-Cessa R., Chao H.J.: Maximum Weight Matching Dispatching Scheme in Buffered Clos-Network Packet Switches. In Proc. IEEE International Conference on Communications 2004 - ICC-2004, Paris, France, 2004, pp. 830-844.
• [6] Pun K., Hamdi M.: Dispatching schemes for Clos-network switches. Computer Networks no. 44, 2004, pp.667-679.
• [7] Jiang Y., Hamdi M.: A fully desynchronized round-robin matching scheduler for a VOQ packet switch architecture. In Proc. IEEE High Performance Switching and Routing 2001– HPSR 2001,May 2001, pp. 407-411.
• [8] Hui J.Y., ArthursE.: A Broadband Packet Switch for Integrated Transport. IEEE J. Sel.Areas Commun., vol. 5, no. 8, Oct. 1987, pp. 1264-1273.
• [9] Lin Chuan-Bi, Rojas-Cessa R.: Frame Occupancy-Based Dispatching Schemes for Buffered Three-stage Clos-Network switches. In Proc. 13th IEEE International Conference on Networks 2005.
• [10] Rojas-Cessa R., Lin Chuan-Bi: Scalable Two-stage Clos-Network Switch and Module-First Matching. In Proc. High Performance Switching and Routing 2006 – HPSR 2006, pp. 303-308.
• [11] Kleban J., Wieczorek A.: CRRD-OG: A packet Dispatching Algorithm with Open Grants for Three-Stage Buffered Clos-Network Switches. In Proc. High Performance Switching and Routing 2006 – HPSR 2006, pp. 315-320.
• [12] Kleban J., Sobieraj M.,Węclewski S.: TheModifiedMSM Clos Switching Fabric with Efficient Packet Dispatching Scheme. In Proc. IEEE High Performance Switching and Routing 2007 – HPSR 2007, New York, May 30 to June 1, 2007.
• [13] Kleban J., Santos H.: Packet Dispatching Algorithms with the Static Connection Patterns Scheme for Three-Stage Buffered Clos-Network Switches. In Proc. IEEE International Conference on Communications 2007 – ICC-2007, 24-28 June 2007, Glasgow, Scotland.
• [14] Clos C.: A Study of Non-Blocking Switching Networks. Bell Sys. Tech. Jour., 1953, pp. 406-424.