Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Online Call Admission in Optical Networks with Larger Wavelength Demands

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-6890
  • In the problem of \emph{Online Call Admission in Optical Networks}, briefly called \textsc{oca}, we are given a graph $G=(V,E)$ together with a set of wavelengths~$W$ and a finite sequence $\sigma=r_1,r_2,\dots$ of calls which arrive in an online fashion. Each call~$r_j$ specifies a pair of nodes to be connected and an integral demand indicating the number of required lightpaths. A lightpath is a path in~$G$ together with a wavelength~$\lambda \in W$. Upon arrival of a call, an online algorithm must decide immediately and irrevocably whether to accept or to reject the call without any knowledge of calls which appear later in the sequence. If the call is accepted, the algorithm must provide the requested number of lightpaths to connect the specified nodes. The essential restriction is the wavelength conflict constraint: each wavelength is available only once per edge, which implies that two lightpaths sharing an edge must have different wavelengths. Each accepted call contributes a benefit equal to its demand to the overall profit. The objective in \textsc{oca} is to maximize the overall profit. Competitive algorithms for \textsc{oca} have been known for the special case where every call requests just a single lightpath. In this paper we present the first competitive online algorithms for the general case of larger demands.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Sven Krumke, Diana Poensgen
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:Call Admission; Colorability; Competitive Analysis; Optical Networks; Routing and Wavelength Allocation
MSC-Klassifikation:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q25 Analysis of algorithms and problem complexity [See also 68W40]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B18 Communication networks [See also 68M10, 94A05]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
Datum der Erstveröffentlichung:07.05.2002
Schriftenreihe (Bandnummer):ZIB-Report (02-22)
ZIB-Reportnummer:02-22
Verlagspublikation:Appeared in: Graph-Theoretic Concepts in Computer Science. 28 Intern. Workshop, WG 2002, Cesky Krumlov, Czech Republic, June 13-15, 2002, revised papers. L. Kucera (ed.) Springer 2002. LNCS 2573. Pp. 333-344
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.