تخطي إلى التنقل الرئيسي تخطي إلى البحث تخطي إلى المحتوى الرئيسي

Non-preemptive scheduling of optical switches

  • Alex Kesselman
  • , Kirill Kogan

نتاج البحث: نتاج بحثي من مؤتمر › محاضرة › مراجعة النظراء

12 اقتباسات (Scopus)

ملخص

Many high-speed routers today use Input-Queued (IQ) architectures with a crossbar switching fabric based on optical technology. Packets in the input queues are divided into cells of unit length and the goal is to find a schedule of minimum makespan that forwards all packets to the output ports. The problem is complicated since in optical switches so called configuration delay, that is the time required to reconfigure the switching fabric, is non-negligible with respect to the cell transmission time. We aim to design a scheduler whose complexity does not depend on the number of packets in the input queues. Thus, we focus on the Non-Preemptive Bipartite Scheduling (NPBS) problem, where each input queue is connected to each output port in at most one configuration. We demonstrate that the NPBS problem is NP-hard for any value of the configuration delay and approximation within a ratio smaller than 7/6 is NP-hard as well. For the offline version of the NPBS problem, we show that a simple greedy algorithm achieves an approximation factor of 2 for arbitrary configuration delay. Then we consider the online version of the NPBS problem, where the switch gathers the incoming traffic periodically and then schedules the accumulated batches (batch scheduling). We propose a scheduling algorithm which guarantees strict delay for any admissible traffic provided that the switch has a moderate speedup of two.

اللغة الأصليةالإنجليزيّة
الصفحات1840-1844
عدد الصفحات5
حالة النشرنُشِر - 2004
منشور خارجيًانعم
الحدثGLOBECOM'04 - IEEE Global Telecommunications Conference - Dallas, TX, الولايات المتّحدة
المدة: 29 نوفمبر 2004 → 3 ديسمبر 2004

!!Conference

!!ConferenceGLOBECOM'04 - IEEE Global Telecommunications Conference
الدولة/الإقليمالولايات المتّحدة
المدينةDallas, TX
المدة29/11/04 → 3/12/04

بصمة

أدرس بدقة موضوعات البحث “Non-preemptive scheduling of optical switches'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا