Subject: Futures trading in bandwidth

From: Mark Handley <[email-masked]>
Date: Thu, 25 May 95 17:33:35 +0100

Wacky idea number 437....

--------

Bandwidth Agencies, Reservation, Advance Booking and Futures Markets
====================================================================

(From a conversation between Mark Handley, Steve Hailes and Zheng
Wang, and an idea of Ian Wakeman's)

Reservation on a per connection basis is wasteful of router
time/state and link bandwidth.

Advance booking of a connection is a seriously difficult problem.  You
don't want to have to book bandwidth in the routers of a network in
advance, and you don't want to have to pin a route because the route
you get at one time may not be possible or optimal at the time of its
usage.  Advance booking of a links in the internet is even more
difficult if divorced for the actual network itself.  

Reservation is of limited use without advance booking.  So long as a
connection uses a small proportion of a link's bandwidth, then if a
connection works at the start of a conference, there's a good chance
it'll carry on working - so why bother with the reservation?  If it
doesn't work at the start of the conference, your reservation'll be
refused anyway.

Thus we introduce the concept of bandwidth agencies.  A user that
wishes to book a conference approaches a bandwidth agency, which then
attempts to ensure that it has available bandwidth booked between the
sites mentioned.  However, this isn't normally done by reserving
bandwidth on a per-connection basis, but by ensuring that the agency
has sufficient bandwidth booked on the backbones involved.  As
agencies deal with large numbers of connections, the reserved
bandwidth can be bought in bulk on the equivalent of a futures market,
and can be traded between agencies as required.  It's up to the agency
to ensure that it has purchased sufficient bandwidth to satisfy its
customers demand and to take advantage of statistical multiplexing of
its connections, or to trade more bandwidth from another agency or
from the link service provider when it gets its estimates wrong.

Agencies also assist with the problem of billing for reservations -
each service provider traversed by a connection will want to bill for
that reservation.  This becomes a nightmare from an accounting point
of view when a particular conference "connection" needs to be billed
by many different service providers.  Agencies have a long standing
relationship with service providers, or approach local agencies when
they have no existing relationship with the service provider.  As
bandwidth is bought on a futures market, service providers have a
reasonable amount of time to establish an agency's credentials (if
they don't already have a trust relationship with the agency), and
don't have to deal with so many customers.  The client who books the
conference only has to deal with a single agency.  The receivers of
the conference are then billed by the client for encryption keys to
receive the conference if the cost needs to be re-distributed.

Now, how would this work in practice?  

CBQ can support the necessary hierarchy of bandwidth allocations
between agencies on a particular link.  It's up to an agency to police
it's clients and mark non-complient data for later drop at the access
points to ensure that they don't use more bandwidth than the agency
has available, or if they do, that the correct client gets dropped
when no spare bandwidth can be borrowed from another agency in the
same hierarchy.

On demand allocations can be supported by approaching an agency and
attempting to make an RSVP reservation.  Agencies should have booked
enough bandwidth for predicted unbooked "calls".  If not, then either
the agency attempts to trade bandwidth from another agency, or sells
the "call" to another agency to handle.  Either way, unbooked calls
are likely to be more expensive than booked calls at peak times.

Agencies may also wish to support best effort realtime traffic (such
as Mbone audio).  A receiver wishing to receive such a conference can
request it from an agency, and the conference will be allocated from
the agencies traffic allocation, subject to being dropped if reserved
traffic does not leave sufficient bandwidth in the agencies allocation
and not enough bandwidth can be borrowed for the class from elsewhere.

If multiple agencies request the same traffic on a particular link,
only one of their bandwidth allocations is debitted for it (chosen on
a random basis).

The tricky bit is matching booked bandwidth to CBQ classes on links.
It appears necessary that this is closely tied to multicast routing.
Just because best effort unicast traffic takes a particular path
doesn't mean that an agencies bandwidth allocation will be assigned to
that route by the service provider.  Thus it appears we need PVMRP to
do this.  

It all gets a bit fuzzy around here....

----------
Jon's comment on this:

> ok - the bottom line is that the money for the "unlimited bandwidth"
> net of the future could be all raised in 1 day, if we simply start
> bidding for bandwidth, and committ all the bandwidth from now til
> then, and then start upping the price, we can pay for anything
 
> the mind is milo minderbindered.... 
-----------

---

From: Steve Jackowski <[email-masked]>
Date: Thu, 25 May 1995 11:43:50 -0900 (PDT)

Mark,

We are in process of implementing an advanced booking 
facility as part of our Service Manager product.  A 
limited function system will be shipped in late July with 
a fully functional model in September.  Our first customer 
is ARPA.

As I respond to your message, I'll point out problems 
we've solved as well as a couple ideas to go above and 
beyond.

> time/state and link bandwidth.

This is certainly true of advanced reservations as I 
stated at the last intserv meeting.  It can also be true 
of realtime reservations if there is no mechanism for 
preemption of existing reservations.  We have added a 
mechanism in ST-2 to divide reservations into two basic 
classes and then individual priorities for each class.  
The two classes are Scheduled and Unscheduled.  If there 
is insufficient resource to initiate a Scheduled 
reservation, any unscheduled reservation can be preemted.  
The 'vicitim selection' algorithms are something I won't 
go into now but are actually quite interesting.  A 
scheduled reservation cannot be preempted by anything 
other than a higher priority scheduled reservation.  Of 
course this shouldn't happen if the 'bandwidth agency' is 
doing its job correctly.  In our system, if a scheduled 
reservations runs beyond its committed time, it becomes an 
unscheduled reservation of the same priority.  

In our system, preemtion can be done explicitly by the 
Service Manager.  However, it is normally done by 
endstations or routers when the admission control finds 
that there is insufficient resource to admit a higher 
precedence/priority reservation.  

> from the link service provider when it gets its estimates wrong.

Our approach has been to include a topology database in 
the Service Manager.  We track bandwidth availability for 
the endpoints and the edge routers.  We work with standard 
calendaring tools which can coordinate and set up 
conferences.  When, for example, a videoconference is 
scheduled, the calendar tool ensures the participants are 
available, but then include one additional resource: the 
network.  If a network resource is involved in a scheduled 
event, our Analysis engine is invoked to assess the 
viability of the event.  It then adds scheduled events 
to the database and associates them with the required 
resouces.  If network resources are unavailable (a link is 
already booked to the max), the calendar tool discovers 
that one if the resources is unavailable.  We also have 
mechanisms to actually initiate the events by using the 
calendar tool to send alarms to all participants.  These 
alarms can contain executable scripts.   Eventually the 
Analysis Engine will be expanded to assess network 
capability beyond the edges.  

> receive the conference if the cost needs to be re-distributed.
This is an interesting topic we're just beginning to 
explore.  We have a rudimentary bulling system in the 
Service Manager.  However, we've just begun investigating 
some technology jointly developed by SUN and Agorics of 
Los Altos, CA which has some very sophisiticted bidding 
mechanisms for negotiating and paying for network 
resources.  I'll let you know what we find out.

> when no spare bandwidth can be borrowed from another agency in the

In our SUN implementations, we will use CBQ.  We have also 
devloped NDIS and ODI-based mechanisms where the Service 
Manager sets Scheduled and Unscheduled bandwidth on a per 
user, per applications, or per NIC basis.  The local 
admission control uses this as does the packet 
classifier.  Borrowing and link sharing are supported.

> and not enough bandwidth can be borrowed for the class from elsewhere.
As mentioned above this is critical.  In ARPA terms this 
is 'free play.'  However, it is surprisingly important 
that even unscheduled reservations receive some service 
guarantee.  It is particularly frustrating to attempt a 
call, get connected, and get dropped before any work gets 
done.  This is where victim selection get challenging.

> that route by the service provider.  Thus it appears we need PVMRP to

If I understand this issue, our simplistic solution was to 
inform the Service Manager as each part of a reservation 
is build (as part of admission control).  This isn't 
terribly efficient and doesn't scale well.  I'm hoping the 
Agorics technology will assist in solving this problem.

Steve

---

From: Curtis Villamizar <[email-masked]>
Date: Thu, 25 May 1995 15:37:14 -0400

> Wacky idea number 437....

:-)  Only 437?

> doesn't work at the start of the conference, your reservation'll be

If a significant portion of traffic or the vast majority is elastic or
is real time but capable of bandwidth shedding, real time reservations
will always (from a practical standpoint) suceed and elastic traffic
will just move slower.

Reservation would be needed, but not advanced reservation, if links
where often congested but carried a significant amount of elastic
traffic and/or shedable real time bandwidth.  Just plain RSVP with
appropriate queueing treatment would work.

Ignore this: Do you currently know of any part of the world in which
you make an advanced reservation before making a phone call?  :-)

I will now counter my own argument.  For very large reservations your
statement may be true.

Curtis

---

From: "Amit Gupta" <[email-masked]>
Date: Wed, 31 May 1995 11:22:53 PDT

Some random thoughts on advance booking

Three interesting papers on "advance booking" at NOSSDAV 95; 
 URL=http://spiderman.bu.edu/nossdav95/NOSSDAV95.html 

  M. Degermark, T. Kohler, S. Pink and O. Schelen, 
	"Advance Reservations for Predicted Service"
  D. Ferrari, A. Gupta and G. Ventre, 
	"Distributed Advance Reservation of Real-Time Connections"
  L. Wolf, L. Delgrossi, R. Steinmetz, S. Schaller and H. Wittig, 
	"Issues of Reserving Resources in Advance"

"Bandwidth agencies" look a lot like Virtual Private Networks; though 
they may request link bandwidth (and other resources) in big chunks,
they will still have to do the internal book-keeping on a 
per-connection basis...

 Trading bandwidth mechanism: changing CBQ class allocations 
(or changing the partition allocations in the Tenet protocols)

 While advance bookings immensely improve the utility of resource 
reservation/allocation, reservations are not completely useless
without advance booking....

 Interactions with routing: definitely very interesting; routing decisions
should be made on the "future load" and not on the current load (except if
we assume that the current load predicts well what the future load will
look like, and ....); this "future load" becomes pretty tricky when we
consider variations, e.g., consider a new flow request for 8am to 10am;
if some links are loaded during 8am to 9am while others are loaded during
9am to 10am ....

 Advance booking makes the routing problem "off-line" and also permits
re-routing connections/flows before they are used; this can be pretty
useful for load-balancing, plus it also gets rid of some of the
objections to "pinning" the routes in advance....

 Is it futures trading, or trading "future bandwidth"?

 Comments/suggestions welcome

 thanks

 -amit