DE60300907T2

DE60300907T2 - Verfahren und System für Ressourcenallokation in Echtzeit zwischen mehreren Einheiten

Info

Publication number: DE60300907T2
Application number: DE60300907T
Authority: DE
Inventors: Arnaud Delenda
Original assignee: France Telecom SA
Current assignee: Chartoleaux KG LLC
Priority date: 2002-04-15
Filing date: 2003-04-09
Publication date: 2006-05-18
Anticipated expiration: 2023-04-10
Also published as: US20040024687A1; EP1355233B1; ATE298903T1; US7788133B2; DE60300907D1; EP1355233A1; ES2244849T3

Description

GEBIET DER ERFINDUNG
Die Erfindung betrifft ein Verfahren und ein System zum Zuteilen einer der Menge nach teilbaren Ressource an mehrere Entitäten in Echtzeit.
Zur Vereinfachung der Terminologie wird in der Folge mit Entität jeder logische Agent, d. h. Software-Agent oder Automat bezeichnet, der fähig ist, ein automatisches Verfahren zur Beteiligung an der Nachfrage einer Ressource bzw. der Anforderung eines Betriebsmittels über ein Telekommunikationsnetz auszuführen.
Die Entität, die eine Ressource anfordert, ist die Nutzer-Entität des Zuteilungssystems. Diese Entität wird über ihren Automaten (oder ihre Software) wirksam.
Die Entität, die die Ressource hält, ist die Anbieter-Entität. Im Falle einer Telekommunikationsressource kann der Anbieter beispielsweise die Fernmeldegesellschaft sein.
Das Ressourcenmanagement-System ist eine Entität, die zwischen den Nutzer-Entitäten und den Anbieter-Entitäten angeordnet ist, wobei sie an das Telekommunikationsnetz angeschlossen ist.
Diese dritte Entität wird durch jeden logischen Agenten, d. h. Software-Agenten oder Automaten, der fähig ist, von einem automatischen Verfahren zur Verarbeitung von zu einem gegebenen Zeitpunkt erhaltenen Anforderungen im Hinblick auf eine Zuteilung einer durch Berechnen bestimmten Ressourcenmenge an Nutzer-Entitäten des Systems Gebrauch zu machen, verwirklicht.
Die Erfindung findet folglich auf jedes System zur Zuteilung einer der Menge nach teilbaren Ressource Anwendung, sobald die Menge dieser Ressource begrenzt ist und eine oder mehrere Entitäten zu einem bestimmten Zeitpunkt eine bestimmte Menge dieser Ressource erfordern und die Gesamtnachfrage das Angebot der Anbieter-Entität übersteigt.
Tatsächlich stellt sich auf der Ebene eines Management-Systems eines Telekommunikationsnetzes oder einer von mehreren Entitäten gemeinsam genutzten Anlagenausrüstung das Problem der Verteilung der von diesem System oder dieser Anlagenausrüstung bereitgestellten Ressourcen unter ihren verschiedenen Entitäten sowie der Durchführung des Nachfrage- bzw. Anforderungsmechanismus für die Zuteilung.
Eines der Probleme, die ein solcher Mechanismus lösen soll, ist die Durchführung einer Arbitrage zwischen den verschiedenen Nutzer-Entitäten, sobald die kumulierte Nachfrage dieser verschiedenen Entitäten die Gesamtmenge der verfügbaren Ressource (nämlich das Angebot) übersteigt. Wenn die Ressourcenmenge, die allen von den Nutzer-Entitäten vorgebrachten Nachfragen entspricht, kleiner als das Angebot bleibt, kann das System den Entitäten die Gesamtheit dessen, was sie nachgefragt haben, zuteilen, und es gibt kein Problem.
STAND DER TECHNIK
Es gibt bis heute zahlreiche Verfahren, um die Ressourcenzuteilung zu verwirklichen:

– Als Erstes kann auf alle Mechanismen hingewiesen werden, die ausgehend von der Reihenfolge des Eintreffens wirksam werden: FIFO, LIFO, ... Bei einem FIFO- (First In First Out) Mechanismus werden die Entitäten zuerst bedient, die ihre Nachfrage am frühesten vorgebracht haben. Im Gegensatz dazu wird bei einem LIFO- (Last In First Out) Mechanismus derjenige bedient, der als Letzter eine Nachfrage vorgebracht hat.
– Es gibt noch weitere Mechanismen, die keine Entität ausschließen: Die Arbitrage erfolgt bezüglich der Ressourcenmenge, die jeder Entität gewährt wird. Als Arbitrageregel wird beispielsweise eine Regel benutzt, die die gewährten Mengen im Verhältnis zu den nachgefragten Mengen festlegt. Es wird auf den Stand der Technik verwiesen, den das Dokument D1 – US-A-6 005 852 darstellt.

Diese Mechanismen sind wirtschaftlich gesehen nicht immer sehr effizient. Die Übereinstimmung zwischen dem Angebot (der angebotenen Menge) und der Nachfrage (den gewünschten oder erhaltenen Mengen) kann tatsächlich schwer zu erreichen sein.
Mit derartigen Mechanismen gibt es Perioden der Flaute, in denen die Nachfrage geringer als die verfügbare Ressourcenmenge bleibt, und Perioden der Überlastung, in denen die Nachfrage die verfügbaren Ressourcen weit übersteigt.
Außerdem sind diese Mechanismen verhältnismäßig statisch. Sie sind nicht fähig, sich anzupassen und sachdienlich zu bleiben, wenn das Angebot und die Nachfrage nach der Ressource von Seiten der Abnehmer-Entitäten starke und schnelle Schwankungen erfahren.
Eine mögliche Lösung, um dieses Kriterium der Effizienz und der Anpassungsfähigkeit des Ressourcenzuteilungsverfahrens zu erfüllen, besteht darin, ein Zuteilungsverfahren anzuwenden, das auf markttypischen Mechanismen beruht, und speziell vom Typ der Auktion in mehreren Einheiten (die Ressource ist teilbar): Die Ressource, die betrachtet wird, besteht aus mehreren Einheiten.
Beispielsweise kann auf die von Klemperer entwickelte Theorie verwiesen werden (Klemperer P., Auction Theory: A Guide to the Litterature, Journal of Economic Surveys, 13 (3), 227–86, 1999).
Leider betreffen die meisten der aus- und angeführten Arbeiten zu Nachfragen in Form von auf mehrere Einheiten bezogenen Auktionen nur theoretische Güter.
Einige weitere Arbeiten befassen sich mit Nachfragen in Form von Auktionen, die im Allgemeinen auf Betreiben öffentlicher Einrichtungen oder von Regulierungsbehörden ablaufen, in deren Verlauf bestimmte knappe Ressourcen oder Nutzungsrechte angeboten werden. Ein bemerkenswertes Beispiel betrifft die Lizenzen der Funkverkehrsfrequenzen: der GSM- oder UMTS-Frequenzen.
In dem einen wie in dem anderen Fall gibt es keinen konkreten Managementmechanismus, der sich empfiehlt, um das Verfahren zur Zuteilung der Ressource zu steuern.
Es ist bis heute nur ein einziges konkretes Verfahren bekannt, welches das Problem, mit dem sich der Anmelder beschäftigt hat, angeht.
Es handelt sich um einen Mechanismus zur Nachfrage bzw. Anforderung in Form eines Gebots, im Folgenden "PSP" (Akronym für "Progressive Second Price" (engl.)) genannt, der von Nemo Semret 1999 in einer Doktorarbeit an der Columbia University vorgeschlagen und rechnerisch erprobt worden ist (Semret N.: Market Mechanisms for Network Ressource Sharing, Philosophy Doctorate, Columbia, 1999). Dieses "PSP"-Verfahren ist ein Mechanismus zum Management von Nachfragen, die in Form von Geboten auftreten. Dieses Verfahren versucht, das Vickrey-Prinzip im Falle einer in mehrere Einheiten teilbaren Ressource einzuführen.
Gemäß diesem Management-Verfahren wird außerdem die Verwirklichung des Kompensationsausschlussprinzips bei der Berechnung einer zeitlich veränderlichen Größe (oder Variablen) für einen gegebenen Zeitpunkt angewendet.
Ein Interessent, der sich an einer Nachfrage beteiligt und eine bestimmte Menge der Ressource erwirbt, bezahlt für einen Wert der Variablen, der ihm von jenen zugestanden wird, die durch sein Auftreten eine bestimmte Menge der Ressource eingebüßt haben.
Die Gesamtheit dieser Menge entspricht höchstens der Menge, die er erhalten hat. Selbstverständlich erhalten die "Teilnehmer" die Ressource, die die höchsten Werte für die Variable geboten haben.
Der PSP-Auktionsmechanismus für die Zuteilung einer Ressource hat Anlass für eine Patentanmeldung gegeben, die am 28. September 2000 unter der Nummer WO 00/57 323 veröffentlicht worden ist.
Der Mechanismus zum Zuteilen einer Ressource, der durch die PSP-Auktionen wie in dieser Anmeldung beschrieben festgelegt ist, wird durch einen iterativen Verhandlungsprozess zwischen drei Entitäten verwirklicht, die sich jeweils durch unterschiedliche Ziele auszeichnen:

– dem logischen Agenten "Anbieter der Ressource", der versucht, diese Ressource gemäß im Voraus festgelegten Kriterien für einen Wert der Variablen, der so hoch wie möglich ist, zu liefern;
– den logischen Agenten "Interessenten", die ihrerseits anstreben, eine bestimmte Menge dieser Ressource nach ihren eigenen im Voraus festgelegten Kriterien zu den besten Konditionen zu erlangen, wobei sich eine beste Kondition durch ein Paar (Menge, Wert der Größe) auszeichnet, das von jedem Interessenten abhängt;
– dem logischen Agenten zum Management der Zuteilung, dessen Ziel es ist, zu erreichen, dass die beiden vorhergehenden Klassen von Entitäten aufs Beste zufrieden gestellt werden.

Die Rolle des logischen Zuteilungsmanagement-Agenten kann von dem Anbieter der Ressource übernommen werden.
Theoretisch führt der PSP-Auktionsmechanismus zu einem Gleichgewicht; er weist jedoch Nachteile auf.
Zuallererst ist die Geschwindigkeit der Konvergenz nicht völlig zufrieden stellend. Selbst wenn eine unveränderliche Anzahl von Entitäten angenommen wird, die während einer bestimmten Zeitdauer an einer Nachfrage (d. h. in dem speziellen Fall an einer Nachfrage vom Typ Gebot) beteiligt sind, sind viele Iterationen des Zuteilungsmanagementverfahrens erforderlich, um das Gleichgewicht zu erreichen, das der maximalen Zufriedenheit aller Entitäten, die an dieser Nachfrage beteiligt sind, genügt.
Operativ äußert sich dieser Mangel an Konvergenz

– entweder in einer sehr großen Menge an Nachrichten zwischen den Entitäten, die an einer Nachfrage beteiligt sind, und der Zuteilungsmanagement-Entität. Dies zieht einen umfangreichen Meldungsverkehr in dem System nach sich. Außerdem bringt dies viele Berechnungen mit sich, die von den beteiligten Entitäten und der Anbieter-Entität ausgeführt werden, falls entschieden wird, die Iterationsfrequenz zu erhöhen, um das Gleichgewicht schneller zu erreichen.
– oder in einer Verschlechterung des Verfahrens im Vergleich zu seinem optimalen Gleichgewicht, wenn die Frequenz der wiederholten Ausgabe von Nachfragen bzw. Anforderungen, die auf neue Bedingungen abgestimmt sind (Menge, Wert der Größe) (jede Minute oder häufiger), begrenzt wird. Die beteiligten Entitäten können neue Nachfragen bzw. Anforderungen mit neuen Bedingungen nicht vor Ablauf dieser minimalen Zeit wegschicken.

Im Falle einer dynamischen Arbeitsweise können die Nutzer-Entitäten des Systems fortwährend in das Zuteilungssystem eintreten oder dieses verlassen, wobei die Zeit zwischen zwei Verarbeitungen von Nachfragen, die auf neue Bedingungen abgestimmt sind, die gleiche Größenordnung wie die durchschnittliche Zeit zwischen dem Zugang oder dem Abgang einer neuen Entität annehmen kann.
Unter diesen Bedingungen erreicht der iterative PSP-Verarbeitungsprozess niemals das Gleichgewicht, bei dem die Nutzer-Entitäten des Ressourcenzuteilungsmanagement-Systems maximal zufrieden gestellt sind. Dieses System ist ständig in einem Übergangszustand, der möglicherweise vom optimalen Gleichgewicht entfernt ist.
Außerdem ist ein weiterer Nachteil, dass das PSP-Verfahren, wie es von Nemo Semret beschrieben worden ist, zulässt, dass Nutzer-Entitäten eine Koalition bilden, um für sie günstige Bedingungen durchzusetzen.
Diese beiden Nachteile sind durch den iterativen Charakter des Mechanismus verursacht, wobei sie besonders ärgerlich im Hinblick auf die Unparteilichkeit sind, die jeder Ressourcen-Zuteilungsmechanismus zwingend respektieren muss, wobei gleichzeitig vorher festgelegte Regeln zu beachten sind.
ERFINDUNG
Die vorliegende Erfindung hat zum Ziel, ein Verfahren und ein System vorzuschlagen, die nicht die Nachteile des Standes der Technik aufweisen.
Gemäß der Erfindung wird der Schritt der Bestimmung der Ressourcen- bzw. Betriebsmittelmenge, die jedem logischen Nutzer-Agenten zugeteilt wird, nach der Verarbeitung der Anforderung zu einem gegebenen Zeitpunkt, zu dem von jeder Entität, die in einer bestimmten Periode auftritt, nur eine einzige Anforderung ausgegeben worden ist, ausgeführt.
Die Erfindung betrifft insbesondere ein Verfahren zum Zuweisen eines Betriebsmittels an n logische Entitäten oder Agenten, die das Betriebsmittel anfordern, mittels eines Management-Systems für das Betriebsmittel, wobei das Verfahren insbesondere dadurch gekennzeichnet ist, dass es während einer vorgegebenen Zeitdauer umfasst:

– Empfangen einer von jedem anfordernden Agenten ausgegebenen Anforderung in Form einer Betriebsmittelanforderungsfunktion s_i(p), worin p eine variable Größe ist, wobei diese Anforderungsfunktionen im Voraus definierte, abnehmende und stetige positive Funktionen sind,
– Verarbeiten aller empfangenen Anforderungen während der vorgegebenen Zeitdauer, um die Betriebsmittelmenge zu bestimmen, die jedem anfordernden Agenten zuzuweisen ist, wobei diese Verarbeitung die folgenden Schritte umfasst:
– Berechnen einer Dateneinheit, die einer Größe, die Gleichgewichtsgröße p* genannt wird, entspricht, anhand der Summe S aus n Anforderungsfunktionen s_i(p) mittels der Beziehung: S(p*) = Qworin Q die Dateneinheit bezüglich der verfügbaren Menge ist und S(p) die Gesamtanforderung ist, die der Summe der Anforderungen s_i(p) jedes Agenten für jeden Wert, den die Größe p annehmen kann, entspricht, S(p) = s1(p) + s2(p) + ... + si(p) + ... + sn(p)
– Berechnen der Daten, die der Menge a_i entsprechen, die für diese Gleichgewichtsgröße p* jedem Agenten i zuzuweisen ist, anhand ihrer Anforderungsfunktion s_i, derart, dass: ai = si(p*),
– Verwenden der Daten, die durch die Berechnung erhalten werden, durch das Management-System, um die entsprechenden Betriebsmittelmengen zuzuweisen, und Aufzeichnen dieser Daten, um sie an ein Betriebssystem zu liefern.

Gemäß einem weiteren Merkmal besteht es darin, die Anforderungsfunktion s_i(p) in jedem anfordernden logischen Agenten zu programmieren.
Gemäß einem weiteren Merkmal besteht es darin, eine Funktion U'_i(q) in jedem anfordernden logischen Agenten i zu programmieren,
wobei jeder anfordernde Agent i, der während der vorgegebenen Zeitdauer teilnimmt, somit durch sein Interesse daran gekennzeichnet ist, eine Menge q der globalen Betriebsmittel Q zu erhalten, und zwar durch seine Nutzenfunktion U_i(q) oder durch eine Grenznutzenfunktion U'_i(q), die dem Erwerb einer zusätzlichen Einheit beigemessen wird, wobei U'_i(q) die Ableitung von U_i(q) ist,
und bei jeder erneuten Teilnahme

– die Anforderungsfunktion s_i(p) zu bestimmen, indem die inverse Funktion der Funktion U'_i(q) berechnet wird, wobei der anfordernde logische Agent seine Anforderung ausgibt, indem er diese Funktion schickt.

Gemäß einem weiteren Merkmal besteht die Lieferung der Anforderungsfunktion darin, an das Management-System Daten zu schicken, die m Parametern entsprechen, die diese Anforderungsfunktion beschreiben.
Gemäß einem weiteren Merkmal ist die Nutzenfunktion eine Polynomfunktion der Form:
was eine Nachfrage- bzw. Anforderungsfunktion S(p) ergibt: S(p) = max(0; qmax – αp)wobei p der Wert der Größe ist, die der Anforderer für eine zusätzliche Betriebsmitteleinheit jenseits von q = s(p) zu akzeptieren bereit ist.
Gemäß einem weiteren Merkmal ist die Nutzenfunktion eine Funktion der Form:
wobei Ln der natürliche Logarithmus ist,
was eine Nachfrage- bzw. Anforderungsfunktion S(p) ergibt: S(p) = qmax·exp(–α·p)wobei p der Wert der Größe ist, die der Anforderer für eine zusätzliche Betriebsmitteleinheit jenseits von q = s(p) zu akzeptieren bereit ist.
Gemäß einem weiteren Merkmal schickt der anfordernde logische Agent seine Anforderung, wobei er nur zwei Parameter (m = 2) liefert, die seine Anforderungsfunktion kennzeichnen, wobei diese Parameter der Koeffizient α, der den Wert der von dem Anforderer annehmbaren Größe angibt, und q_max, die maximale Menge, die er zu erhalten wünscht, sind, wobei diese Anforderung für mehrere aufeinander folgende Teilnahmen gleich sein kann.
Gemäß einem weiteren Merkmal umfasst die Berechnung des Wertes der Größe p, die jeden logischen Agenten kennzeichnet, nach der Verarbeitung aller Anforderungen während der vorgegebenen Dauer:

– eine Berechnung des Wertes der Gesamtgröße C_i(s) der Menge a_i, die einem anfordernden logischen Agenten i zugewiesen wird, um die Menge a_i(s) zu erhalten, wenn dieser Letztere die Funktion s_i ausgegeben hat, wobei auf der Grundlage des Kompensationsausschlussprinzips diese Berechnung anhand der folgenden Beziehung erfolgt:
worin für den anfordernden Agenten j a_j ^s seine Zuweisung in Gegenwart des anfordernden Agenten i repräsentiert und a_j ⁰ seine Zuweisung bei dessen Abwesenheit repräsentiert, wobei sich die von j verschiedenen teilnehmenden Anforderer in diesem Fall die Menge a_j ⁰ zuweisen sehen, während sie in der aktuellen Situation auf Grund des Vorhandenseins von i nur a_j ^s haben, wobei s_j ^–1 die inversen Anforderungsfunktionen der teilnehmenden anfordernden Agenten j sind.

Gemäß einem weiteren Merkmal ist das Management-System ein Telekommunikationsbetriebsmittelmanagement-System, und das Betriebsmittel ist das Durchlassband.
Ein weiterer Gegenstand der vorliegenden Erfindung betrifft ein Betriebsmittelmanagement-System mit Mitteln zum Zuweisen des Betriebsmittels an n anfordernde logische Agenten über ein Telekommunikationsnetz, insbesondere dadurch gekennzeichnet, dass diese Zuweisungsmittel umfassen:

– Mittel zum Empfangen einer Anforderung, die von jedem anfordernden Agenten in Form einer Betriebsmittelanforderungsfunktion s_i(p) ausgegeben wird, worin p eine variable Größe ist, wobei diese Anforderungsfunktionen im Voraus definierte, abnehmende und stetige positive Funktionen sind,
– Verarbeitungsmittel für alle Anforderungen, die während einer vorgegebenen Zeitdauer empfangen werden, um die jedem anfordernden Agenten zuzuweisende Betriebsmittelmenge zu bestimmen, wobei diese Verarbeitungsmittel umfassen:
– Mittel zum Berechnen einer Dateneinheit, die einem Wert der Größe, die Gleichgewichtsgröße p* genannt wird, entspricht, anhand der Summe S aus n Anforderungsfunktionen s_i(p) mittels der Beziehung: S(p*) = Qworin Q die Dateneinheit bezüglich der verfügbaren Menge ist, und S(p) die Gesamtanforderung ist, die der Summe der Anforderungen s_i(p) jedes anfordernden Agenten für jeden Wert, den die Größe p annimmt, entspricht, S(p) = s1(p) + s2(p) + ... + si(p) + ... + sn(p),
– Mittel zum Berechnen der Daten, die der Menge a_i entsprechen, die für diesen Gleichgewichtswert p* jedem anfordernden Agenten i zuzuweisen ist, anhand seiner Anforderungsfunktion s_i, derart, dass: ai = si(p*),
– Mittel zum Zuweisen entsprechender Betriebsmittelmengen und zum Aufzeichnen dieser Daten, um sie an ein Betriebssystem zu liefern.

Gemäß einem weiteren Merkmal sind die Mittel zum Zuweisen des Betriebsmittels durch einen Rechner des Server-Typs verwirklicht, der dafür programmiert ist, wobei der Server mit der Telekommunikationsnetz-Anlage verbunden ist, die mit den Anforderungen jener Betriebsmittel belastet ist, die zwischen den Entitäten, die sie anfordern, aufgeteilt werden sollen.
Gemäß einem weiteren Merkmal umfassen die anfordernden logischen Agenten Mittel zum Aufzeichnen wenigstens einer Anforderungsfunktion und Mittel, um Anforderungen in Form von Anforderungsfunktion zu schicken.
In dem Fall, in dem die Anforderungsfunktion durch nur zwei Parameter beschrieben wird, umfassen die anfordernden Agenten Mittel, um bei jeder neuen Anforderung ein Wertepaar für die Parameter zu wählen und es an den Server zu liefern.
Gemäß einem weiteren Merkmal sind die anfordernden logischen Agenten durch programmierte Automaten verwirklicht, um die Anforderungen auszuführen und um mit dem Server einen Dialog zu führen.
Gemäß einem weiteren Merkmal sind die Automaten durch mobile Software-Agenten gebildet, die in dem Server angeordnet sein können.
In einem bevorzugten Beispiel ist die Ressource bzw. das Betriebsmittel ein Telekommunikationsbetriebsmittel.
In diesem Fall kann die zuzuteilende Ressource die Bandbreite sein oder die Ports einer Netzzugangseinrichtung.
KURZBESCHREIBUNG DER ZEICHNUNG
Weitere Besonderheiten und Vorteile der Erfindung werden beim Lesen der Beschreibung deutlich, die nachstehend beispielhaft und nicht einschränkend anhand der Zeichnung gegeben ist, worin
1A und 1B eine Nutzenfunktion U_i und ihre Ableitung U'_i (Grenznutzen) zeigen;
2A und 2B drei Nutzenfunktionsbeispiele für die gleiche maximale Menge (q_max) und die entsprechenden Grenznutzen zeigen;
2C die Nachfragefunktionen zeigt, die den Grenznutzenfunktionen von 2B entsprechen;
2D zwei besondere Beispiele für die Nutzenfunktion zeigt;
2E die Nachfragefunktionen zeigt, die den Nutzenfunktionen von 2D entsprechen;
3 ein Beispiel für Nachfragefunktionen s₁, s₂ von zwei Interessenten zeigt;
4 die Berechnung des Wertes der Größe p für dieses einfache Beispiel mit zwei Interessenten schematisch darstellt;
5 das allgemeine Schema eines Systems zur Ausführung des Verfahrens veranschaulicht;
6 ein Schema zur Verwirklichung von logischen Agenten, die Nutzer des Systems sind, veranschaulicht.
Der Ressourcenmanagement-Mechanismus, der vorgeschlagen wird, um eine in mehrere Einheiten teilbare Ressource mehreren Nutzern zuzuteilen, beruht auf der Tatsache, dass jeder Interessent i, der Nutzer der Ressource ist, ein Interesse daran hat, einen Teil (eine Menge) a_i der Gesamtressource Q, die zu einem gegebenen Zeitpunkt zur Verfügung steht, zu erhalten. Das Interesse der Nutzer-Entität des Zuteilungsmanagement-Systems wird mittels einer zeitlich veränderlichen Größe p gemessen.
Dieser Mechanismus ermöglicht, jedem der Nutzer die "richtigen" Mengen a_i der Ressource für einen Wert C_i zu gewähren.
Bei dem vorgeschlagenen Verfahren ist jede Entität angehalten, ihre tatsächliche Wertschätzung (oder auch ihren Nutzen) der Erlangung der Ressourcenmenge (Fall des Interessenten) oder den Wert der Größe p_I, zu dem sie bereit ist, die Ressource abzugeben (Fall des Anbieters), anzugeben.
Der Anbieter-Agent wird nämlich als ein Agent angesehen, der die Gesamtmenge der Ressource Q nachfragt.
Dieser Letztere kann die Abgabe der Ressource unterhalb eines Minimum-Grenzwertes für die Größe meiden. Das Risiko dieser Methode besteht darin, dass eine bestimmte Menge der Ressource nicht verteilt bzw. vertrieben wird (da sie von ihm selbst gehalten wird).
Der vorgeschlagene Mechanismus passt sich an Schwankungen der Anzahl der Interessenten und an ihre Prädisposition, die Ressource anzufordern, an. Es kann Perioden der Flaute mit wenigen Interessenten und Perioden der Überlastung mit viel mehr Interessenten geben.
Der vorgeschlagene Mechanismus erlaubt dann die Regulierung der Nachfrage in Abhängigkeit von dem konstanten Angebot der Ressource Q mittels einer veränderlichen Messgröße.
Um während einer Periode der Überlastung eine größere Ressourcenmenge zu erlangen, muss der Interessent einen höheren Wert der Messgröße akzeptieren. Hingegen kann er in Perioden der Flaute eine große Ressourcenmenge für einen geringeren Wert dieser Größe erlangen.
Der Mechanismus gemäß der Erfindung ist nicht iterativ. Er führt zu einem Gleichgewicht bei einer höheren Zufriedenheit der Interessenten bei Entgegennahme von nur einer Nachfrage, die von jedem Interessenten vorgebracht wird, der sich während einer vorgegebenen Zeitdauer an einer Bewerbung um Zuteilung beteiligt.
Außerdem werden die auf diese Weise bestimmten Daten an ein Betriebssystem geliefert, welches im Falle mehrerer Einheiten das Vickrey-Prinzip anwen det, das auf dem Kompensationsausschluss beruht, um für jede abgegebene Anforderung eine charakteristische Dateneinheit zu berechnen.
Der vorgeschlagene Management-Mechanismus läuft folgendermaßen ab:

– Ein Anbieter hat irgendeine Menge Q einer teilbaren Ressource oder eines teilbaren Gutes zur Verfügung. Bei einer Telekommunikations- oder Netzanwendung kann es sich typisch um die Bandbreite oder auch um logische Zugangsports zu einer Anlagenausrüstung handeln.
– n Entitäten sind nachfragend, was bedeutet, dass sie während einer vorgegebenen Zeitdauer um die Verteilung dieser Ressource konkurrieren. Jede davon positioniert sich auf einer Nutzenfunktion U_i für die Menge q, die sie haben möchte. Es handelt sich im Grunde genommen um die von dem Interessenten vorgenommene Bewertung seines Interesses an einer bestimmten Ressourcenmenge.

Die Wahl einer Nutzenfunktion könnte völlig den nachfragenden bzw. anfordernden Agenten überlassen sein; jedoch wird aus praktischen Gründen der Umsetzung bevorzugt, den nachfragenden bzw. anfordernden Agenten vorzuschlagen, sich für das Aushandeln auf einer Auswahl von vorher zu diesem Zweck in dem programmierten Automaten definierten Nutzenfunktionen zu positionieren. Praktisch wählt der programmierte Automat dazu die Nutzenfunktion, die er bei einer Nachfrage bzw. Anforderung verwenden wird.
Die Kenntnis der Nutzenfunktion U_i(q) eines Interessenten ermöglicht, davon seine Nachfragefunktion s_i(p) abzuleiten. Konkret ist die Nachfragefunktion eines Interessenten das Inverse der Grenznutzenfunktion U'_i(q). Folglich wird eine kleine sprachliche Unkorrektheit begangen, denn die auf diese Weise konstruierte Nachfragefunktion gibt den Wert der Nachfrage q eines teilnehmenden Interessenten in Abhängigkeit von einem bestimmten Wert der Größe p, dem so genannten Grenzwert, an, den der Interessent bereit ist, einer Ressourcenmenge, die zwischen q und q + δq enthalten ist, wobei δq eine kleine Menge ist, beizumessen, wohingegen herkömmlich eine Nachfragefunktion die Menge q der Ressource, die der Käufer zu erwerben bereit ist, in Abhängigkeit von einem Durchschnittswert für die Größe p der Ressource angibt.
Die Entität, nämlich der Server 200 in 5, der eine Nachfrage (d. h. die Gesamtheit der von den Interessenten bzw. Anforderenn während einer vorgegebenen Zeitdauer gesendeten Anforderungen) managt, erfasst die Nachfrage- bzw. Anforderungsfunktionen s_i(p) der verschiedenen Käufer und hat Kenntnis von der Gesamtmenge, die zugeteilt werden kann.
Um sich an einer Nachfrage bzw. Anforderung zu beteiligen, gibt ein Nutzer seine Nachfragefunktion s_i(p) an, die in der Praxis das Inverse seiner Grenznutzenfunktion für die Ressource sein kann.
Selbstverständlich können die Interessenten eine "erlogene" Nachfragefunktion mitteilen (nicht die Wahrheit sagen, d. h. nicht ihre wahre Bewertung der Ressource äußern). Das Verfahren gemäß der vorliegenden Erfindung verwendet jedoch einen Mechanismus zur Berechnung der Ressourcenzuteilung, der jeden Interessenten veranlasst, die entsprechende Nachfrage zu schicken, denn diese verschafft ihm die besten Zuteilungsbedingungen.
Ein Maß für die besten Bedingungen ist der Unterschied zwischen dem Nutzen, den ihm der Erwerb einer Ressourcenmenge verschafft, und dem Wert der Größe, den er für diese Menge akzeptieren muss. Der Anmelder hat gezeigt, dass die Bekanntgabe seiner wahren Nachfragefunktion für jeden Interessenten bzw. Anforderer eine dominante Strategie ist.
Gemäß der Erfindung besitzt folglich jeder Interessent bzw. Anforderer i eine Wertschätzung für den Erwerb einer Menge q_i der Ressource, die in einer Nutzenfunktion U_i(q) ≥ 0 Ausdruck findet, wobei diese Wertschätzung im Grunde genommen eine private Dateneinheit ist. Das Berechnen der Ableitung dieser Funktion, nämlich von U'_i(q), ergibt die Grenznutzenfunktion, die der Nutzer i dem Erwerb einer zusätzlichen Einheit der Ressource beimisst.
Mathematisch ist die Funktion U_i(q) dadurch gekennzeichnet, dass sie den folgenden Bedingungen genügt:

• Ui(0) = 0
• U_i ist ableitbar und konkav;
• U'_i ≥ 0 ist fallend und stetig. Es handelt sich dabei um die von der Funktion U(i) abgeleitete Funktion. Sie beschreibt den Grenznutzen des Interessenten bzw. Anforderers i durch die Ressource, d. h. den Wert der Größe, den er zu akzeptieren bereit ist, um über jene Einheit, die er schon erlangt hat, hinaus eine Einheit der Ressource zu erlangen.

1A und 1B veranschaulichen eine allgemeine Form der Funktionen U_i(q) und U'_i(q).
Wie zu sehen ist, steigt die Nutzenfunktion eines Interessenten bzw. Anforderers 100i (5) stetig mit der Menge, die er erlangen kann, an, wobei jedoch dieser Anstieg schwach gekrümmt (konkav) ist. Das heißt in dem Maße, wie die erlangte Menge größer wird, nimmt das Interesse an einer zusätzlichen Einheit ab. Im Extremfall gibt es für jeden Anwender einen Grenzwert (Schwellenwert) der Ressourcenmenge, jenseits dessen dieser Nutzer der Erlangung einer zusätzlichen Einheit kein Interesse mehr beimisst (d. h. der Wert der Größe ist null).
Bei jeder neuen Nachfrage bzw. Anforderung (Schritt des Managements einer neuen Nachfrage bzw. Anforderung) nimmt der Server 200 alle Anforderungen in Form von Nachfrage- bzw. Anforderungsfunktionen s_i (eine Funktion pro Interessent bzw. Anforderer i) entgegen.
Anhand dieser Informationen bestimmt der Server 200 für jeden Wert der Größe p die Gesamtnachfrage S, die die Summe der einzelnen Nachfragen ist. Der Server 200 berechnet den Gleichgewichtswert p*, der Angebot und Nachfrage in Übereinstimmung bringt, so dass: S(p*) = Q,wobei Q die Gesamtmenge, die zuzuteilen ist, und folglich das Gesamtangebot darstellt.
Nachdem der Gleichgewichtswert p* auf diese Weise definiert worden ist, kann der Server 200 die Ressourcenzuteilungen a₁, a₂, ..., a_i, ..., a_n für jeden Interessenten bzw. Anforderer ermitteln, indem er folgende Berechnung vornimmt: ai = si(p*) für jeden Interessenten bzw. Anforderer (i = 1 bis n)
Mittels dieser Berechnung bestimmt der Server als Zuteilung für jeden Anforderer den Wert seiner Nachfrage- bzw. Anforderungsfunktion für den Wert p*.
Der Server 200 ordnet jedem Anforderer eine auf diese Weise berechnete zugeteilte Menge zu und informiert die Anforderer auch über den Gleichgewichtswert der Größe p, der dem Mechanismus als Grundlage dient.
Einige Interessenten bzw. Anforderer werden nicht bedient werden können (für den Wert p* können nämlich Nutzer j eine Nachfrage von null haben, d. h. s_j(p*) = 0).
Dieser Zuteilungsmanagement-Schritt wird bei der Inbetriebnahme des Systems zur Ressourcenzuteilung in vorher festgelegten regelmäßigen Intervallen wiederholt.
Die Wiederholfrequenz der Nachfragen (Senden von neuen Anforderungen durch die Anforderer) wird so gewählt, dass sie nicht zu hoch ist, um die kalkulatorischen Betriebsmittel nicht zu stark in Anspruch zu nehmen und/oder das Netz mit Nachrichten zur Signalisierung zwischen der anfordernden Software 100i der Nutzer und dem Server 200 zu belasten.
Diese Frequenz muss jedoch ausreichen, um die Entwicklungen zu berücksichtigen: Zugänge oder Abgänge von Interessenten bzw. Anforderern, Veränderung der Nachfragefunktionen von beteiligten Interessenten bzw. Anforderern und gegebenenfalls Veränderung der verfügbaren Ressourcenmenge.
Ein zweiter Schritt des Verfahrens besteht dann darin, den Wert der entsprechenden Größe zu berechnen, d. h. Bestimmung des Wertes für jeden Interessenten bzw. Anforderer i. Dieser Wert wird im Ergebnis der Berechnung des folgenden Integrals erhalten:
Diese Relation gibt den Gesamtwert C_i(s) an, den der Interessent bzw. Anforderer i für die Erlangung der Menge a_i(s), die in dem vorhergehenden Schritt bestimmt worden ist, akzeptieren muss, wenn die Nachfrage s ist. Für den Interessenten bzw. Anforderer j stellt a_j ^s seine Zuteilung im Falle der Anwesenheit des Interessenten bzw. Anforderers i und a_j ⁰ seine Zuteilung in dem Fall, in dem er abwesend wäre, dar (Wenn der Interessent bzw. Anforderer i nicht anwesend wäre, dann würden sich die anderen Beteiligten j die Menge a_j ⁰ zuteilen sehen, während es in der derzeitigen Situation auf Grund der Anwesenheit von i nur a_j ^s gibt).
Die Berechnung des Wertes der Größe p lässt die inverse Funktion s_j ^–1 der Nachfragefunktion s_j der anderen Teilnehmer j auf den Plan treten, denn es wird ein Wert in Abhängigkeit von einer schon definierten Menge und nicht eine Menge in Abhängigkeit von einem gegebenen Wert gesucht.
Im Folgenden werden zwei Beispiele für die Nutzenfunktion und die entsprechenden Nachfragefunktionen gegeben.
Selbstverständlich wird jede Nutzenfunktion (und Nachfragefunktion) gewählt werden können, sobald sie die vorangehend dargelegten Bedingungen erfüllt. Diese Funktionen können durch m Parameter beschrieben sein, die z. B. wahlweise einer bestimmten Anzahl von charakteristischen Punkten im Anschluss an eine Diskretisierung (Digitalisierung) der Funktion entsprechen.
Gemäß einem ersten Beispiel kann die Nutzenfunktion die folgende Polynomfunktion sein:
was eine Nachfrage- bzw. Anforderungsfunktion S(p) ergibt: S(p) = max(0; qmax – αp)wobei p der Grenzwert genannte Wert ist, den der Interessent bzw. Anforderer für eine zusätzliche Einheit der Ressource bzw. des Betriebsmittels jenseits von q = s(p) zu akzeptieren bereit ist.
In diesem ersten Beispiel hat jeder Interessent i eine Polynom-Wertschätzungsfunktion U_i (vom Grad 2) bis zu dem Punkt, der der maximalen Menge q_max des Interessenten i entspricht; darüber hinaus ist diese Funktion dann konstant.
Gemäß einem weiteren Beispiel kann die Nutzenfunktion die folgende Exponentialfunktion sein:
wobei Ln der natürliche Logarithmus ist, was eine Nachfragefunktion S(p) ergibt: S(p) = qmax·exp(–α·p)wobei p der Grenzwert genannte Wert ist, den der Interessent bzw. Anforderer für eine zusätzliche Einheit der Ressource bzw. des Betriebsmittels jenseits von q = s(p) zu akzeptieren bereit ist.
In diesen zwei Fällen können die Nutzenfunktion und die Grenznutzenfunktion U'_i (von U_i abgeleitete Funktion) und folglich die Nachfragefunktionen (inverse Funktion des Grenznutzens) durch nur zwei Parameter q_max und α beschrieben werden, wobei

– q_max die maximale Ressourcenmenge ist, über die der nachfragende bzw. anfordernde Agent nicht hinausgehen wird, um zusätzlich von der Ressource zu erhalten (Grenznutzen null), und
– α die Stärke des Interesses des Nutzers an der Ressource beschreibt.

Je größer α ist, desto schneller nimmt dieses Interesses bei der Erhöhung des Wertes der Größe p der Ressource ab. Es handelt sich um einen Koeffizienten, der die Akzeptanz-Prädisposition des Interessenten angibt.
Wenn vorgesehen ist, verschiedene Typen von vorher definierten Funktionen zu verwenden (Funktion 1, 2, 3, ... usw.), müssten im Grunde genommen drei Parameter geliefert werden, nämlich die Parameter wie zuvor definiert und ein dritter Parameter, der den gewählten Funktionstyp bezeichnet (Funktion 1 oder 2 oder 3 der Liste vorher definierter Funktionen).
2D veranschaulicht die Nutzenfunktionen, die den zwei vorhergehenden Beispielen entsprechen. 2E veranschaulicht die Nachfragefunktionen, die den zwei Nutzenfunktionen von 2D entsprechen.
In diesen Beispielen brauchen die Abnehmer dem Server 200 nicht mehr die vollständig definierten Nachfragefunktionen für alle möglichen Mengen anzugeben, sondern es genügen die zwei Parameter q_max und α (jeder Interessent bzw. Nachfrager schickt seine Nachfrage- bzw. Anforderungsfunktion).
Die Ausgabe der Anforderung besteht dann darin, zwei Parameter anzugeben, und zwar in diesem Fall das Paar (q_max, α).
Im Falle einer Anwendung der Erfindung auf die Zuteilung eines Telekommunikationsbetriebsmittels wie etwa die Bandbreite

– entspricht der Wert q_max der maximalen Mengenleistung, die der Nutzer anfordert;
– ist der Koeffizient α aus einer Gesamtheit von zuvor abgespeicherten Werten gewählt, wobei er dem Streben des Nutzers, diese maximale Mengenleistung zu erlangen, entspricht (verschiedene Werte von p ermöglichen, mehr zu erhalten).

2A und 2B zeigen den Verlauf, den die Nutzenfunktion und ihre Ableitung für drei Interessenten annehmen, die den gleichen Maximalwert für die Menge haben.
Der Koeffizient α entspricht der Steigung der Geraden (Nachfragefunktion) in 2C.
Jedoch ist, statt den Nutzer eine beliebige Nutzenfunktion wählen zu lassen, welche die vorangehend dargelegten Eigenschaften des Anstiegs und der Stetigkeit aufweist, wie zuvor vorteilhaft vorgesehen, dem Interessenten vorzuschlagen, sich anhand einer beschränkten Auswahl von Möglichkeiten zu positionieren.
Diese Auswahl umfasst entsprechend diesen zwei Parametern: die von dem Interessenten angeforderte maximale Mengenleistung und das Prädispositionsniveau, d. h. ein Schwellenwert der Größe, um diese maximale Mengenleistung aufs Beste zu erlangen.
Außerdem kann vorgesehen sein, eine Auswahl aus mehreren Prädispositionsparametern vorzuschlagen.
Beispielsweise kann die Definition von mehreren Dienstklassen programmiert werden: "Gold" für einen vorher festgelegten Wert von α, "Silber" für einen weiteren Wert oder "Bronze" für noch einen weiteren Wert.
Die Klasse "Gold" entspricht einer stärkeren Prädisposition als die Klasse "Silber", die ihrerseits einer stärkeren Prädisposition als die Klasse "Bronze" entspricht.
Zum besseren Verständnis werden nun diese Mechanismen anhand eines einfachen Beispiels, bei dem es nur zwei Interessenten gibt, ausführlicher beschrieben.
In dem Beispiel, das gegeben wird, hat der Interessent 1 eine Maximalmenge q_max, die größer als jene des Interessenten 2 ist, aber seine Prädisposition, den Wert der Größe p zu akzeptieren, ist schwächer (es handelt sich um Werte, die sich der Interessent zum Zeitpunkt der Nachfrage bzw. Anforderung festgesetzt hat). Anhand dieser gewonnenen Informationen berechnet der Server 200 (für jeden Wert p) die Summe S dieser zwei Nachfragefunktionen.
Der Server 200 kann dann den Marktgleichgewichtswert bestimmen, der Angebot und Nachfrage ausgleicht. Dieser Wert entspricht dem Wert p*, so dass S(p*) = Q. Denn S(p*) entspricht der Gesamtnachfrage bei dem Wert p*, und Q ist definitionsgemäß die angebotene Menge der Ressource.
Bei bekanntem p* werden die Zuteilungen a₁ und a₂ für jeden der Interessenten bestimmt. Jeder Interessent erhält die Menge, die seiner Nachfragefunktion für den Wert p* entspricht, nämlich: a₁(s) = s₁(p*) und a₂(s) = s₂(p*).
3 veranschaulicht den Zuteilungsschritt, der soeben für den Fall von zwei Interessenten beschrieben worden ist, deren Nachfragefunktionen affin sind (Polynom-Nutzenfunktion vom Grad 2).
In einem weiteren Schritt des Verfahrens werden die auf diese Weise bestimmten Daten an ein Betriebssystem geliefert, das in das Management-System selbst integriert sein kann. Diese Verarbeitung der Daten besteht darin, den Wert der Größe für jeden der Interessenten bzw. Anforderer zu berechnen. Dieser Schritt wendet das an früherer Stelle erwähnte Kompensationsausschlussprinzip an. In diesem einfachen Beispiel teilt der Interessent bzw. Anforderer 1 mit, dass er bereit ist, das Inverse von s₁ zu akzeptieren.
In der Tat stellt s₁(p) die von dem Interessenten 1 nachgefragte Menge dar, wenn der Wert der Größe p ist. Wenn der Interessent 2 nicht an der Nachfrage beteiligt wäre, hätte der Interessent 1 seine nachgefragte Maximalmenge erhalten, die mit q₁ bezeichnet wird. Um von seiner Zuteilung a₁ zu seiner Maximalmenge q₁ zu gelangen, akzeptiert der Interessent 1 einen Wert, der dem Integral des Inversen von s₁ entspricht. (Es wird eine Berechnung eines Integrals ausgeführt, da von einem Grenzwert zu einem Gesamtwert übergegangen wird.)
4 veranschaulicht diese Operationen. Die Fläche des mit Z₂ bezeichneten schraffierten Bereiches entspricht dem Ergebnis.
5 stellt das System zur Durchführung des Verfahrens schematisch dar. Es kann sich beispielsweise um ein Telekommunikationsbetriebsmittelmanagement-System handeln.
Eine praktische Umsetzung der operativen Durchführung des soeben beschriebenen Zuteilungsmechanismus wird durch eine Gesamtheit von anfordernden Automaten oder Software-Agenten 100i bewerkstelligt. Jeder Interessent bzw. Anforderer i (aber auch der Anbieter) programmiert seine Nutzenfunktion und folglich seine Nachfragefunktion (in den angegebenen Beispielen nur durch zwei Parameter definiert) in seinem Automaten oder Software-Agenten 100i.
Im Grunde genommen können diese Funktionen vorher definiert werden, und der nachfragende bzw. anfordernde logische Agent braucht dann nur eine davon auszuwählen. Diese logischen Agenten führen mit dem Server 200 einen Dialog, um ihre Betriebsmittel-Zuweisungsanforderung vorzunehmen.
Der Server 200 oder das Betriebsmittelmanagement-System ist über Verbindungen 210 und 110 an ein Telekommunikationsnetz 300 und an logische Abnehmer-Agenten 100i angeschlossen. Dieser Server 200 umfasst einen Automaten, der für die Durchführung der oben genannten Berechnungen, wobei von dem beschriebenen Mechanismus Gebrauch gemacht wird, programmiert ist. Dieser Automat umfasst eine Verarbeitungseinheit vom Typ Prozessor 201, Speichermittel 202, eine Eingabe/Ausgabe-Schnittstelle 204. Der Automat umfasst Verbindungen nach außen: 210 zu dem Netz 300 und 110 zu den anfordernden logischen Agenten 100i.
6 veranschaulicht ein Ausführungsbeispiel für einen Automaten, der in den Abnehmer-Agenten 100i integriert ist. Dieser Automat umfasst einen Prozessor 101, der mit Speichermitteln verbunden ist, die durch den Block 102 symbolisch dargestellt sind. Diese Speichermittel umfassen wenigstens einen Direktzugriffsspeicher als Arbeitsspeicher, einen Programmspeicher vom Typ ROM oder EEPROM, der das Programm zur Lieferung von Nutzenfunktionen und Nachfragefunktionen des Anforderers und für den Dialog mit dem Server enthält. Der Prozessor 101 und die Speicher 102 sind durch einen Bus 103 verbunden, der seinerseits an einem Eingabe/Ausgabe-Port zu einer Nachrichtenverbindung 110 mit dem Server 200 durchgeschaltet wird.
Wenn die Ausführung mittels Software-Agenten verwirklicht wird, können diese mobil sein.
Diese Software-Agenten 100i können sich in der Nähe des Anforderers i, d. h. in dem Steuerungsterminal des Nutzers, befinden, wenn dieser Letztere eine ständige Interaktion über seine Nachfrage- bzw. Anforderungsfunktion wünscht.
In dem Fall, in dem die Nachfrage- bzw. Anforderungsfunktion eines Anforderers stabil bleibt, kann sich der Software-Agent für das Anforderungsmanagement des Anforderers dann in der Nähe des Zuweisungsmanagement-Servers 200, d. h. in dem Management-Server, befinden.
In dem Schema von 5 entspricht das gemeinschaftliche Betriebsmittel Q der Bandbreite der zwischen dem Management-Server und dem "Netz" verwirklichten Verbindung.
Der Vorteil einer "Auslagerung" des Anforderungsmanagement-Agenten des Anforderers besteht in der Verringerung des Befehlsdatenstroms, der zwischen dem Server und den anfordernden Agenten fließt, sowie in der Beschleunigung des Dialogs zwischen dem Management-Automaten des Anforderers und dem Zuweisungsmanagement-Server. Wenn sich ein anfordernder Agent in der Nähe des Servers befindet, erzeugt er keine Anforderungsnachricht über das Netz.
Der Zuweisungsmanagement-Server berücksichtigt alle Anforderungen der Nutzer und nimmt die Berechnung des Ergebnisses der Nachfrage bzw. Anforderung gemäß dem beschriebenen Mechanismus vor.
Im Fall der gemeinsamen Nutzung der Bandbreite einer Verbindung kann der Server 200 ein Software-Server sein, der in dem Router zur Bündelung oder in irgendeiner anderen Einrichtung zur Bündelung lokalisiert ist.
Nach Abschluss seines Entscheidungsprozesses steuert der Server dann die Anlagenausrüstung (in dem oben erwähnten Beispiel den Router zur Bündelung), damit diese jedem der Anforderer die festgesetzte Menge zuweist.
Für andere Betriebsmittel kann dies ein anwendungsspezifischer Server sein. Es wird festgehalten, dass der Server und die Automaten über Netzverbindungen verbunden sind und folglich die Ressource bzw. das Betriebsmittel Netz (Bandbreite) nutzen.
Das Verfahren der Erfindung ist an eine dynamische Funktionsweise vollkommen angepasst. Die Interessenten bzw. Anforderer können sich jederzeit einloggen, um sich an der Nachfrage bzw. Anforderung zu beteiligen. Der Mechanismus ermöglicht dann, für jeden die Zuteilung und den Wert der Größe p erneut zu berechnen.
Im Unterschied zu PSP-Auktionen wird das Gleichgewicht automatisch erreicht, denn die anfordernden Automaten senden die Anforderung nicht jedes Mal erneut, sondern sie senden eine einzige Anforderung, welche die Nachfrage- bzw. Anforderungsfunktion enthält, die ihrer Wertschätzung der Ressource bzw. des Betriebsmittels entspricht.
Beispielsweise kann die zeitlich veränderliche Größe, die ermöglicht, eine Ressource zu kennzeichnen, der Preis sein. Es wird sich nicht um eine "absolute" Geldsumme handeln, sondern um einen Preis pro Zeiteinheit der Nutzung.
Die Interessenten bzw. Anforderer sind Abnehmer/Kunden des Anbieters der Ressource.
Wenn es sich um ein Telekommunikationsnetz-Betriebsmittel handelt, wird die Summe, die der Netzkunde zahlen muss, folglich das Produkt aus diesem Preis pro Einheit und der Dauer, die er mit dem Netz verbunden bleiben wird, sein.
Die Berechnungen des zu zahlenden Preises, d. h. der Kosten, werden ebenfalls aufgezeichnet, um an einen Server geliefert zu werden, der mit der Inrechnungstellung betraut ist.
Diese kann in einer Erhöhung des Kundenkontos um die zu zahlende Summe oder in einer Verminderung der Anzahl der dem Kundenkonto gutgeschriebenen "Zahlungseinheiten" Ausdruck finden. Dafür übermittelt der Zuweisungsmanagement-Server die erforderlichen Informationen an den mit der Inrechnungstellung beauftragten Server.
Beispielsweise zahlen die Abnehmer × Euros pro erhaltenes Megabit pro Sekunde. Andernfalls würde ein Abnehmer, der eine Ressourcenmenge nur einige Sekunden hält (d. h. dass weitere Nutzer hinzugekommen sind und seine Ressource durch ein günstigeres Gebot teilweise oder vollständig "für sich beansprucht" haben), den gleichen Preis zahlen, wie wenn er diese gleiche Menge über mehrere Tage gehalten hätte.
Die minimale zeitliche Preisfestsetzungseinheit kann das Zeitintervall zwischen zwei Neuverhandlungen der Auktion sein: minimale Haltezeit der Ressource. Der Mechanismus kann so vorgesehen sein, dass es nicht unbedingt notwendig ist, die "zufrieden gestellten" Abnehmer zu zwingen, ihre Anforderung bei jeder Neuverhandlung zu modifizieren; der Zuweisungsmanagement-Server kann nämlich voreingestellt voraussetzen, dass ihre Nachfragefunktion unverändert ist.
Um den Abgang eines Kunden zu erfassen, kann beispielsweise bei jedem Schritt das Zurückschicken aller Nachfragefunktionen durch die Verhandlungsautomaten der Abnehmer vorgesehen werden. Dieses einfache Mittel ermöglicht nämlich, einen Abgang zu erfassen.
Wie deutlich geworden ist, lässt sich, indem nur eine Nachfrage bei einer Verhandlung vorgebracht wird, ein Gleichgewicht erreichen, wobei die Abnehmer ihre wahre Nachfragefunktion und folglich ihre wahre Wertschätzungsfunktion einsetzen. Die Tatsache, dass das angestrebte Gleichgewicht mittels einer einzigen Nachfrage bzw. Anforderung (ohne Iterationsverfahren) erreicht wird, stellt im Vergleich zu bisher einen erheblichen Vorteil dar.
Zu diesem Vorteil kommt im Vergleich zu vorgeschlagenen Mechanismen der Vorteil hinzu, dass der Mechanismus weniger technische Hypothesen über die Eigentümlichkeiten der Abnehmer verlangt. Die einzige Hypothese, die aufgestellt wird, ist, dass die Nachfragefunktionen fallend sein müssen, was völlig natürlich ist: Es ist nämlich nicht vorstellbar, dass ein Kunde bereit ist, die Ressource teurer zu bezahlen (im Sinne des Preises pro Einheit), wenn die Menge, die er nachfragt, zunimmt. Dies würde im Gegensatz zu den "Discount"-Effekten sein, die gewöhnlich anzutreffen sind.
Schließlich werden im Gegensatz zu dem iterativen Verfahren der PSP-Auktionen die Nutzer nicht bei jeder Iteration über die von den anderen Teilnehmern vorgenommenen Anforderungen unterrichtet. Es ist nämlich gezeigt worden, dass diese Informationen Absprachen der Kunden, um beispielsweise weniger zu zahlen, ermöglichten.

Claims

Verfahren zum Zuweisen eines Betriebsmittels an n logische Entitäten oder Agenten, die das Betriebsmittel anfordern, mittels eines Management-Systems (200) für das Betriebsmittel, wobei das Verfahren während einer vorgegebenen Zeitdauer umfasst: – Empfangen einer von jedem anfordernden Agenten (100i) ausgegebenen Anforderung in Form einer Betriebsmittelanforderungsfunktion s_i(p), worin p eine variable Größe ist, wobei diese Anforderungsfunktionen im Voraus definierte, abnehmende und stetige positive Funktionen sind, – Verarbeiten aller empfangenen Anforderungen während der vorgegebenen Zeitdauer, um die Betriebsmittelmenge zu bestimmen, die jedem anfordernden Agenten zuzuweisen ist, wobei diese Verarbeitung die folgenden Schritte umfasst: – Berechnen einer Dateneinheit, die einer Größe, die Gleichgewichtsgröße p* genannt wird, entspricht, anhand der Summe S aus n Anforderungsfunktionen s_i(p) mittels der Beziehung: S(p*) = Q, – worin Q die Dateneinheit bezüglich der verfügbaren Menge ist und – S(p) die Gesamtanforderung ist, die der Summe der Anforderungen s_i(p) jedes Agenten für jeden Wert, den die Größe p annehmen kann, entspricht, S(p) = s1(p) + s2(p) + ... + si(p) + ... + sn(p),– Berechnen der Dateneinheiten, die der Menge a_i entsprechen, die für diese Gleichgewichtsgröße p* jedem Agenten i zuzuweisen ist, anhand ihrer Anforderungsfunktion s_i, derart, dass: –ai = si(p*),– Verwenden der Daten, die durch die Berechnung erhalten werden, durch das Management-System, um die entsprechenden Betriebsmittelmengen zuzuweisen, und Aufzeichnen dieser Daten, um sie an ein Betriebssystem zu liefern, dadurch gekennzeichnet, dass es darin besteht: – eine Funktion U'_i(q) in dem anfordernden logischen Agenten i zu programmieren, – wobei jeder anfordernde Agent i, der während der vorgegebenen Zeitdauer teilnimmt, somit durch sein Interesse daran gekennzeichnet ist, eine Menge q der globalen Betriebsmittel Q zu erhalten, und zwar durch eine Nutzenfunktion U_i(q) oder durch eine Grenznutzenfunktion U'_i(q), die an die Erfassung einer zusätzlichen Einheit U'_i(q), die die Ableitung von U_i(q) ist, angepasst ist, und bei jeder erneuten Teilnahme: – die Anforderungsfunktion s_i(p) zu bestimmen, indem die inverse Funktion der Funktion U'_i(q) berechnet wird, wobei der anfordernde logische Agent seine Anforderung ausgibt, indem er diese Funktion schickt; – und dass: – die Nutzenfunktion eine Polynomfunktion der folgenden Form ist:
was eine Anforderungsfunktion S(p) ergibt: S(p) = max(0; qmax – αp)wobei p der Wert der Größe ist, die der Anforderer für eine zusätzliche Betriebsmitteleinheit jenseits von q = s(p) zu akzeptieren bereit ist, q_max die maximale Menge ist, die er erhalten möchte, α den Wert der von dem Anforderer annehmbaren Größe angibt; – oder eine Funktion der folgenden Form ist:
wobei Ln der natürliche Logarithmus ist, was die folgende Anforderungsfunktion S(p) ergibt: S(p) = qmax·exp(–α·p)wobei p der Wert der Größe ist, die der Abnehmer für eine zusätzliche Betriebsmitteleinheit jenseits von q = s(p) zu akzeptieren bereit ist, q_max die maximale Menge ist, die er erhalten möchte, α den Wert der von dem Anforderer annehmbaren Größe angibt.
Betriebsmittelzuweisungsverfahren nach Anspruch 1, dadurch gekennzeichnet, dass die Lieferung der Anforderungsfunktion darin besteht, an das Management-System Daten zu liefern, die m Parametern entsprechen, die diese Anforderungsfunktion kennzeichnen, wobei m größer oder gleich 2 ist.
Betriebsmittelzuweisungsverfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass der anfordernde logische Agent (100i) seine Anforderung schickt, indem er nur zwei Parameter (m = 2) liefert, die seine Anforderungsfunktion kennzeichnen, wobei diese Parameter der Koeffizient α, der den Wert der von dem Anforderer annehmbaren Größe angibt, und q_max, die maximale Menge, die er zu erhalten wünscht, sind, wobei diese Anforderung für mehrere aufeinander folgende Teilnahmen die gleiche sein kann.
Betriebsmittelzuweisungsverfahren nach Anspruch 1 oder 2 oder 3, dadurch gekennzeichnet, dass die Berechnung des Wertes der Größe p, die jeden logischen Agenten kennzeichnet, nach der Verarbeitung aller Anforderungen während der vorgegebenen Dauer umfasst: – eine Berechnung des Wertes der Gesamtgröße C_i(s) der Menge a_i, die einem anfordernden logischen Agenten i zugewiesen wird, um die Menge a_i(s) zu erhalten, wenn dieser letztere die Funktion s_i ausgegeben hat, was auf dem Kompensationsausschlussprinzip beruht, wobei diese Berechnung anhand der folgenden Beziehung erfolgt:
worin für den anfordernden Agenten j a_j ^s seine Zuweisung in Gegenwart des anfordernden Agenten i repräsentiert und a_j ⁰ seine Zuweisung bei dessen Abwesenheit repräsentiert, wobei sich die von j verschiedenen teilnehmenden Anforderer in diesem Fall die Menge a_j ⁰ zuweisen sehen, während sie in der aktuellen Situation aufgrund des Vorhandenseins von i nur a_j ^s haben, wobei s_j ^–1 die inversen Anforderungsfunktionen der teilnehmenden anfordernden Agenten j sind.
Betriebsmittelzuweisungsverfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass das Management-System (200) ein Telekommunikationsbetriebsmittelmanagement-System ist und dass das Betriebsmittel das Durchlassband ist.
Betriebsmittelmanagement-System, mit Mitteln zum Zuweisen des Betriebsmittels an n anfordernde logische Agenten (100i) über ein Telekommunikationsnetz (300), wobei diese Mittel umfassen: – Mittel zum Empfangen einer Anforderung, die von jedem anfordernden Agenten in Form einer Betriebsmittelanforderungsfunktion s_i(p) ausgegeben werden, worin p eine variable Größe ist, wobei diese Anforderungsfunktionen im Voraus definierte, abnehmende und stetige positive Funktionen sind, – Verarbeitungsmittel (201, 202) für alle Anforderungen, die während einer vorgegebenen Zeitdauer empfangen werden, um die jedem anfordernden Agenten zuzuweisende Betriebsmittelmenge zu bestimmen, wobei diese Verarbeitungsmittel umfassen: – Mittel (201) zum Berechnen einer Dateneinheit, die einem Wert der Größe, die Gleichgewichtsgröße p* genannt wird, entspricht, anhand der Summe S aus n Anforderungsfunktionen s_i(p), mittels der Beziehung: S(p* = Q), – worin Q die Dateneinheit bezüglich der verfügbaren Menge ist, und – S(p) die Gesamtanforderung ist, die der Summe aus den Anforderungen s_i(p) jedes anfordernden Agenten für jeden Wert, den die Größe p annimmt, entspricht, S(p) = s1(p) + s2(p) + ... + si(p) + ... + sn(p).– Mittel zum Berechnen der Dateneinheiten, die der Menge a_i entsprechen, die für diesen Gleichgewichtswert p* jedem anfordernden Agenten i zuzuweisen ist, anhand seiner Anforderungsfunktion s_i, derart, dass: –ai = si(p*),– Mittel (201) zum Zuweisen entsprechender Betriebsmittelmengen und zum Aufzeichnen dieser Daten, um sie an ein Betriebssystem zu liefern, dadurch gekennzeichnet, dass: – jeder anfordernde Agent i Mittel zum Aufzeichnen einer Funktion U'_i(q) umfasst; wobei jeder anfordernde Agent i, der während der vorgegebenen Zeitdauer teilnimmt, somit durch sein Interesse daran gekennzeichnet ist, eine Menge q des globalen Betriebsmittels Q zu erhalten, und zwar durch seine Nutzenfunktion U_i(q) oder durch eine Grenznutzenfunktion U'_i(q), die an die Erlangung einer zusätzlichen Einheit angepasst ist, wobei U'_i(q) die Ableitung von U_i(q) ist, und Mittel umfasst, um bei jeder neuen Teilnahme die Anforderungsfunktion s_i(p) zu bestimmen, indem die inverse Funktion der Funktion U'_i(q) berechnet wird, wobei der anfordernde logische Agent seine Anforderung dadurch ausgibt, dass er diese Funktion schickt, – wobei die Nutzenfunktion eine Polynomfunktion der folgenden Form ist:
was eine Anforderungsfunktion S(p) ergibt: S(p) = max(0; qmax – αp)wobei p der Wert der Größe ist, die der Anforderer für eine zusätzliche Betriebsmitteleinheit jenseits von q = s(p) bereit ist zu akzeptieren, q_max die maximale Menge ist, die er zu erlangen wünscht, α den Wert der von dem Anforderer annehmbaren Größe angibt; oder eine Funktion der folgenden Form ist:
wobei Ln der natürliche Logarithmus ist, was eine Anforderungsfunktion S(p) ergibt: S(p) = qmax·exp(–α·p),wobei p der Wert der Größe ist, die der Abnehmer für eine zusätzliche Betriebsmitteleinheit jenseits von q = s(p) zu akzeptieren bereit ist, q_max die maximale Menge ist, die er zu erlangen wünscht, α den Wert der von dem Anforderer annehmbaren Größe angibt.
Betriebsmittelmanagement-System nach Anspruch 6, dadurch gekennzeichnet, dass die Mittel zum Zuweisen des Betriebsmittels durch einen Rechner des Server-Typs (200) verwirklicht sind, wobei der Server mit der Telekommunikationsnetz-Anlage verbunden ist, die mit den Anforderungen jener Betriebsmittel belastet ist, die zwischen den Entitäten, die sie anfordern, aufgeteilt werden sollen.
Betriebsmittelmanagement-System nach Anspruch 6, dadurch gekennzeichnet, dass die Anforderungsfunktion lediglich durch zwei Parameter gekennzeichnet ist, wobei die anfordernden Agenten Mittel (101) umfassen, um ein Wertepaar für die Parameter bei jeder neuen Anforderung zu wählen und es an den Server zu liefern.
Betriebsmittelmanagement-System nach Anspruch 6 und 7, dadurch gekennzeichnet, dass die anfordernden logischen Agenten (100i) durch programmierte Automaten verwirklicht sind, um die Anforderungen auszuführen und um mit dem Server einen Dialog zu führen.
Betriebsmittelmanagement-System nach Anspruch 6, dadurch gekennzeichnet, dass die Automaten (100i) durch mobile Software-Agenten gebildet sind, die im Server angeordnet sein können.
Betriebsmittelmanagement-System nach Anspruch 6, dadurch gekennzeichnet, dass das Betriebsmittel ein Telekommunikationsbetriebsmittel ist.