BGRP: Sink-Tree-Based Aggregation for Inter-Domain Reservations

        Ping Pan             Ellen Hahne        Henning Schulzrinne
  Bell Labs Research     AT&T Labs Research     Columbia University
 pingpan@bell-labs.com  hahne@research.att.com  hgs@cs.columbia.edu


Abstract:

Resource reservation must operate in an efficient and
scalable fashion, to accommodate the rapid growth
of the Internet.  In this paper, we describe a distributed
architecture for inter-domain aggregated resource reservation
for unicast traffic.  We also present an associated protocol,
called the Border Gateway Reservation Protocol (BGRP), that
scales well, in terms of message processing load, state storage
and bandwidth.  Each stub or transit domain may use its
own intra-domain resource reservation protocol.  BGRP
builds a sink tree for each of the stub domains.  Each
sink tree aggregates bandwidth reservations from all data
sources in the network.  Since backbone routers maintain
only the sink tree information, the total number of
reservations at each router scales linearly with the number 
of Internet domains, N.  (Even aggregated versions
of the current protocol RSVP have a reservation count
that can grow like O(N^2).
BGRP maintains these aggregated reservations using ``soft state.''
To further reduce the protocol message traffic,
routers may reserve bandwidth beyond the current load,
so that some sources can join or leave the tree
without sending messages all the way to the tree root.
BGRP relies on Differentiated Services for data forwarding,
hence the number of packet classifier entries is extremely small.