[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01

INTERNET-DRAFT                                Ljubica Blazevic
                                              Jean-Yves Le Boudec
                                              EPFL-ICA,Switzerland
                                              June 2000


   Distributed Core Multicast (DCM): a routing protocol for many  small
groups  with application to  mobile IP telephony

            <draft-blazevic-dcm-mobility-01.txt>


Status of this Memo

     This document is an Internet-Draft and is in full conformance
     with all provisions of Section 10 of RFC2026.

     Internet-Drafts are working documents of the Internet Engineering
     Task Force (IETF), its areas, and its working groups.  Note that
     other groups may also distribute working documents as
     Internet-Drafts.

     Internet-Drafts are draft documents valid for a maximum of six
     months and may be updated, replaced, or obsoleted by other
     documents at any time.  It is inappropriate to use Internet-
     Drafts as reference material or to cite them other than as
     "work in progress."

     The list of current Internet-Drafts can be accessed at
     http://www.ietf.org/ietf/1id-abstracts.txt

     The list of Internet-Draft Shadow Directories can be accessed at
     http://www.ietf.org/shadow.html.


1. Abstract

   This document specifies a multicast routing protocol called
   Distributed Core Multicast (DCM). It is intended for use within a
   large single Internet domain network with a very large number of
   multicast groups with a small number of receivers. Such a case
   occurs, for example, when multicast addresses are allocated to mobile
   hosts, as a mechanism to manage Internet host mobility. For such
   networks, existing dense or sparse mode multicast routing algorithms
   do not scale well with the number of multicast groups. DCM is based
   on an extension of the centre-based tree approach [1], [2]. It uses
   several core routers, called Distributed Core Routers (DCRs) and a
   special protocol between them. DCM aims: (1) to avoid multicast group
   state information in backbone routers, (2) to avoid triangular
   routing across expensive backbone links, (3) to scale well with the
   number of multicast groups. We analyse how DCM can be used to route
   packets to mobile hosts in cellular IP telephony, where each mobile


Blazevic, Le Boudec                Expires 12/00                [Page 1]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


   host is assigned a multicast address in every domain it visits. The
   benefits of multicasting-based approach to route packets to mobile
   hosts are low latency and no disruption during handover.




2. Introduction

   This document describes a multicast routing protocol called
   Distributed Core Multicast (DCM). DCM is designed to provide low
   overhead delivery of multicast data in a large single domain network
   for a very large number of small groups. This occurs when the number
   of multicast groups is very large (for example, greater than a
   million), the number of receivers per multicast group is very small
   (for example, less than five) and each host is a potential sender to
   a multicast group. In this document, we present how DCM can be used
   in cellular IP telephony. Each mobile host is assigned a multicast
   address in every domain it visits. DCM is then used to route packets
   to mobile hosts that are distributed within a large Internet domain.
   MSP-IP (Mobility support using Multicasting in IP)[3] proposes a
   generic architecture to support host mobility in the Internet by
   using multicasting as the mechanism to route packets to the mobile
   hosts. The routing protocol used in this architecture is out of scope
   of MSP-IP.

   DCM is an extension of an existing multicast routing protocol that
   scales better than other existing protocols when applied to support
   mobile hosts. Recent sparse mode multicast routing protocols, such as
   the protocol independent multicast (PIM-SM) [2] and the core-based
   trees (CBT) [1], build a single delivery tree per multicast group
   that is shared by all senders in the group. This tree is rooted at a
   single centre router called "core" in CBT, and "rendezvous point"
   (RP) in PIM-SM. Both centre-based routing protocols have the
   following potential shortcomings: traffic for the multicast group is
   concentrated on the links along the shared tree, mainly near the core
   router; finding an optimal centre for a group is a NP-complete
   problem and requires the knowledge of the whole network topology [4].
   Current approaches typically use either an administrative selection
   of centres or a simple heuristics [5]. Data distribution through a
   single centre router could cause non optimal distribution of traffic
   in the case of a bad positioning of the centre router with respect to
   senders and receivers. This problem is known as a triangular routing
   problem.

   DCM is based on an extension of the centre-based tree approach and is
   designed for the efficient and scalable delivery of multicast data
   under the assumptions that are satisfied when multicast is used to
   support mobile hosts (large number of multicast groups, a few
   receivers per group and a potentially large number of senders to a
   multicast group). We consider a network model that consists of
   several areas connected via the backbone area (see Figure 1). The


Blazevic, Le Boudec                Expires 12/00                [Page 2]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


   issues addressed by DCM are: (1): to avoid multicast group state
   information in backbone routers, (2): to avoid triangular routing
   across expensive backbone links and (3) to scale well with the number
   of multicast groups.

   The benefits of using the multicasting-based approach to route
   packets to the mobile hosts are low latency and no disruption during
   handover. When a visiting host arrives into the new domain it is
   assigned a temporary multicast address that it keeps as long as it
   stays in the same domain. The base station of the current cell where
   the mobile lies is responsible for joining the multicast tree on
   behalf of the mobile. Mobile hosts communicate with base stations
   over wireless links. Neighbouring base stations that anticipate the
   arrival of the mobile can initiate its group membership registration.
   Thus, a multicast group assigned to a mobile host has a few
   recipients. When the mobile host moves in the new cell, it continues
   to receive packets without disruption. DCM is particularly well
   suited to route packets to mobile hosts since the size of its
   multicast group is small.

   Mobile IP [6] proposal is intended to support macro-level mobility
   and relatively slow moving hosts. Mobile IP requires that after each
   migration of the mobile host its possibly distant home agent is
   informed about the mobile host's current location. In an environment
   with highly mobile hosts, Mobile IP is no longer a good solution. The
   Cellular IP proposal [7] separates local mobility from wide area
   mobility. It proposes a new mobility management within a Cellular IP
   network. Cellular IP can interact with Mobile IP to support wide area
   mobility, that is, mobility between Cellular IP networks. A Cellular
   IP network consists primarily of base stations that keep distributed
   data bases with location information referring to a mobile host. Base
   stations use this information to route packets to the mobile host
   while it is in a Cellular IP Network.

   Our approach, DCM, can be used for a new mobility management approach
   within a large single domain network based on multicasting. DCM is
   not an alternative to Mobile IP [6] since DCM is not a solution to
   wide-area mobility. In contrast, DCM can be used as an alternative to
   Cellular IP within a single domain network. In this document we
   describe how DCM can be in used in conjunction with the Session
   Initiation Protocol (SIP)[8] to support terminal mobility in cellular
   IP Telephony (IPtel). In [9] it is proposed to introduce minor
   changes in SIP to support terminal mobility in IPtel. We expect a
   solution based on DCM to be more scalable, in particular in the
   management of fast or small scale mobility. DCM, when used with SIP,
   is a scalable solution, able to manage a handover of mobile hosts
   with minimal disturbance.


2.1 Distributed Core Multicast (DCM) Protocol Overview

       We consider a network model that consists of several areas


Blazevic, Le Boudec                Expires 12/00                [Page 3]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


      connected via the backbone area. We introduce an architecture that
      is based on several core routers per multicast group, called
      Distributed Core Routers (DCRs).

        - The DCRs in each area are located at the edge of the backbone.
          The DCRs act as backbone access points for the data sent by
          senders inside their area to receivers outside this area. A
          DCR also forwards the multicast data received from the
          backbone to receivers in the area it belongs to. When a host
          wants to join the multicast group M, it sends a join message.
          This join message is propagated hop-by-hop to the DCR inside
          its area that serves the multicast group. Conversely, when a
          sender has data to send to the multicast group, it will send
          the data encapsulated to the DCR assigned to the multicast
          group.
        - The Membership Distribution Protocol (MDP) runs between the
          DCRs serving the same range of multicast addresses. It is
          fully distributed. MDP enables the DCRs to learn about other
          DCRs that have group members.
        - The distribution of data uses a special mechanism between the
          DCRs in the backbone area, and the trees rooted at the DCRs
          towards members of the group in the other areas. We propose a
          special mechanism for data distribution between the DCRs,
          which does not require that non-DCR backbone routers perform
          multicast routing.

      With the introduction of the DCRs close to any sender and
      receivers, converging traffic is not sent to a single centre
      router in the network. Data sent from a sender to a group within
      the same area is not forwarded to the backbone. Our approach
      alleviates the triangular routing problem common to all
      centre-based trees, and unlike PIM-SM, is suitable for groups with
      many sporadic senders.

                                  ++++++++
                                 +        +
                                 +        +
                                 + Area D +
                                 +        +
                                 +        +
                                  +      +
      ++++++++++                 +-+----+-+
     +  Area A  +                |DCR X4  |
     +           +               + ---+----+                   ++++++++++
     +            +            +            +               +            +
     +        (3)  +          +   BACKBONE   +             +             +
     +    A2<<----- +------+ +                + +--------+    (1)        +
     +              |DCR X1|+ <-----+     +--- +| DCR X3 | <<------C1    +
     +    A1 ---->> +------+ +      |     |   + +--------+               +
     +       (1)   +          +  (2)|  (2)|  +            +              +
     +            +             +   |     v +               +   Area C   +
     +           +                +---+----+                 ++++++++++++


Blazevic, Le Boudec                Expires 12/00                [Page 4]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


      +++++++++++                 |DCR X2  |
                                  +-+---+--+
                                  +    ^   +
                                 +     ^    +
                                 +     |    +
                                 +     |(1) +
                                 +     |    +
                                 +     B1   +
                                 +          +
                                 + Area B1  +
                                  +        +
                                   +++++++


       Figure 1: Model of a large single domain network and an overview
      of data distribution with DCM. We show one multicast group M and
      DCRs X1, X2, X3 and X4 that serve a range to which M belongs to.
      Step (1): Senders A1, B1 and C1 send data to the corresponding
      DCRs inside their areas. Step (2): DCRs distribute the multicast
      data across the backbone area to DCR X1 that needs it. Step (3):
      X1 sends data to the local receivers in its area (in this example
      this is A2.


2.2 Terminology

        - DCR. A DCR (Distributed Core Router) is an backbone access
          point for the data sent to multicast address by senders inside
          the same area to members outside the area. A DCR also forwards
          the multicast data received from the backbone to receivers in
          the area it belongs to.
        - DCR serves the multicast address m. A DCR is said to serve the
          multicast address m when it is dynamically elected among all
          the candidate DCRs in the area to act as an access point for
          address m (see Section 3.1).
        - Labelled DCR. A DCR is labelled with the multicast address m
          if the DCR serves m and there are receivers for m in its area.
          A labelled DCR is root of a distribution subtree inside its
          area for m (see Section 3.2).
        - Source DCR. A source DCR for the multicast group m is the DCR
          that receives encapsulated multicast data for m by some source
          inside its area (see Section 3.3).
        - Range. A range is the partition of the set of multicast
          addresses into group of addresses. A DCR can serve several
          ranges of multicast addresses (see Section 3.1).
        - MDP(Membership Distribution Protocol). MDP is used for the
          source DCR in one area to learn about labelled DCRs in other
          areas. MDP is run between DCRs in different areas that serve
          the same range of multicast addresses (see Section 3.4).
        - MDP control multicast address. An MDP control multicast
          address is used for exchanging MDP control messages between
          DCRs that serve the same range of multicast addresses. There


Blazevic, Le Boudec                Expires 12/00                [Page 5]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


          is one MDP control multicast address per range of multicast
          addresses(see Section 3.4).
        - STH(Shortest Tunnel Heuristic). STH is used by the source DCR
          to compute the multicast data distribution tree in the
          backbone. The edges of this tree are tunnels between DCRs.
          (see Appendix)




3. Distributed Core Multicast (DCM) Protocol Functional Description

   In this section, we describe the various elements of DCM. Those are:

     - addressing issues;
     - how hosts join the multicast group;
     - how senders send to a multicast group;
     - how membership information is distributed among DCRs;
     - how multicast data is distributed among DCRs;
     - how multicast data is forwarded from DCR to members of the group
       inside its area.


3.1 Addressing Issues

      In each area there are several routers that are configured to act
      as candidate DCRs. The identities of the candidate DCRs are known
      to all routers within an area by means of an intra-area bootstrap
      protocol [10]. This is similar to PIM-SM with the difference that
      the bootstrap protocol is constrained within an area. This entails
      a periodic distribution of the set of reachable candidate DCRs to
      all routers within an area.

      Routers use a common hash function to map a multicast group
      address to one router from the set of candidate DCRs. For a
      particular group address M, we use the hash function to determine
      the DCR that serves*M.

        *  A DCR is said to serve the multicast group address M when it
          is dynamically elected among all the candidate DCRs in the
          area to act as an access point for address M

      The used hash function is h(r(M),DCR_i). Function r(M) takes as
      input a multicast group address and returns the range of the
      multicast group, while DCR_i is the unicast IP address of the DCR.
      The target DCR_i is then chosen as the candidate DCR with the
      highest value of h(r(M),DCR_j)) among all j in {1,...,J} where J
      is the number of candidate DCRs in an area:

      h(r(M),DCR_i)=max { h(r(M),DCR_j),j=1,..,J }

      One possible example of the function that gives the range is:


Blazevic, Le Boudec                Expires 12/00                [Page 6]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


      r(M)=M&B, where B is a bit mask.

      We do not present here the hash function theory. For more
      information see [11], [10] and [12]. The benefits of using hashing
      to map a multicast group to DCR are the following:

        - We achieve minimal disruption of groups when there is change
          in the candidate DCR set. This means that we have to do a
          small number of re-mappings of multicast groups when there is
          a change in the candidate DCR set. See [11] for more
          explanations.
        - We apply the hash function h(.,.) as defined by the Highest
          Random Weight (HRW) [12] algorithm. This function ensures load
          balancing between candidate DCRs. This is very important,
          because no single DCR serves more multicast groups than any
          other DCR inside the same area. We achieve, by this property,
          that when the number of candidate DCRs increases, the load on
          each DCR decreases.

      All routers in all non-backbone areas should apply the same
      functions h(.,.), r(.).

      Each candidate DCR is aware of all the ranges of multicast
      addresses for which it is elected to be a DCR in its area. There
      is a function m(r(M)) that maps the range of the multicast group
      address M to another multicast address for control purposes. A DCR
      joins a control multicast address that corresponds to a range of
      multicast addresses that it serves. This multicast address is used
      by DCRs in different areas that serve the same range of multicast
      addresses to exchange control information.


3.2 How hosts join the multicast group

      When a host is interested in joining the multicast group M, it
      issues an IGMP[13] join message. A multicast router on its LAN,
      known as the designated router (DR), receives the IGMP join
      message. The DR determines the DCR inside its area that serves M,
      as described in Section 3.1.

      The process of establishing the group shared tree is like in
      PIM-SM [2]. The DR sends a JOIN message towards the determined
      DCR. Sending a JOIN message forces any off-tree routers on the
      path to the DCR to forward a JOIN message and join the tree. Each
      router on the way to the DCR keeps a forwarding state for M. When
      a JOIN message reaches the DCR, this DCR becomes labelled with the
      multicast group M. In this way, the delivery subtree, for the
      receivers of the multicast group M in an area, is established. The
      subtree is maintained by periodically refreshing the state
      information for M in the routers (like in PIM-SM, this is done by
      periodically sending JOIN messages).



Blazevic, Le Boudec                Expires 12/00                [Page 7]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


      Like in PIM-SM, when the DR discovers that there are no longer any
      receivers for M, it sends a PRUNE message towards the nearest DCR
      to disconnect from the shared distribution tree.


3.3 How senders send to a multicast group

      The sending host originates native multicast data, for the
      multicast group M, that is received by the designated router (DR)
      on its LAN. The DR determines the DCR within its area that serves
      M. We call this DCR the source DCR. The DR encapsulates the
      multicast data packet (IP-in-IP) and sends it with a destination
      address equal to the address of the source DCR. The source DCR
      receives the encapsulated multicast data. This is similar to
      PIM-SM where the DR sends encapsulated multicast data to the RP
      corresponding to the multicast group.


3.4 How membership information is distributed among DCRs

      The Membership Distribution Protocol (MDP) is used by DCRs in
      different areas to exchange control information. As is explained
      in Section 3.1, within each non-backbone area, for each range of
      multicast addresses there is one DCR serving that range. DCRs in
      different areas that serve the same range of multicast addresses
      are members of the same MDP control multicast group. This group is
      defined by a MDP control multicast address used for exchanging
      control information. A DCR joins as many MDP control multicast
      groups as the number of ranges of multicast addresses it serves.
      There are as many MDP control multicast groups as there are
      possible ranges of multicast addresses. We do not propose a
      specific protocol for maintaining the multicast tree for the MDP
      multicast group. This can be done by means of an existing
      multicast routing protocol (e.g CBT).

      DCRs that are members of the same MDP control multicast group
      exchange the following control information:

        - periodical keep-alive messages.

        - unicast distance information. Each DCR sends, to the
          corresponding MDP control multicast group, information about
          the unicast distance from itself to other DCRs that it has
          learned to serve the same range of multicast addresses. This
          information comes from existing unicast routing tables and it
          is used for the distribution of multicast data among the DCRs.

        - multicast group information. A DCR, which is labelled with the
          multicast group M, informs DCRs in other areas responsible for
          M that it has receivers for M. In this way, every DCR keeps a
          record of every other DCR that has at least one member for a
          multicast address from the range that the DCR serves. A DCR


Blazevic, Le Boudec                Expires 12/00                [Page 8]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


          should notify all other DCRs when it becomes labelled with a
          new multicast group or no longer labelled with a multicast
          group.

      MDP uses its MDP control multicast addresses and performs flooding
      inside the groups defined by those addresses. An alternative
      approach would be to use MDP servers. This approach leads to a
      more scalable, but also a more complex solution. This approach is
      not studied in detail in this document.




3.5 How multicast data is distributed among DCRs

      The multicast data for the group M is distributed from a source
      DCR to all DCRs that are labelled with M. Since we assume that the
      number of receivers per multicast group is not large, there are
      only a few labelled routers per multicast group. Our goal is to
      perform multicast data distribution in the backbone in such a way
      that backbone routers keep a minimal state information while at
      the same time backbone bandwidth is used efficiently. We propose a
      solution that can be applied in the Internet today. It uses
      point-to-point tunnels to perform data distribution among DCRs.
      With this solution, non-DCR backbone routers do not keep any state
      information related to the distribution of the multicast data in
      the backbone.


Point-to-Point Tunnels

         The DCR that serves the multicast group M keeps the following
         information: (1) a set V of DCRs that serve the same range to
         which M belongs; (2) information about unicast distances
         between each pair of DCRs from V; (3) the set L of labelled
         DCRs for M. The DCR obtains this information by exchanging the
         MDP control messages with DCRs in other areas. In this way, we
         present the virtual network of DCRs that serve the same range
         of multicast group addresses by means of an undirected complete
         graph G=(V,E). V is defined above, while the set of edges E are
         tunnels between each pair of DCRs in V. Each edge is associated
         with a cost value that is equal to an inter-DCR unicast
         distance.

         The source DCR, called S, calculates the optimal tree that
         spans the labelled DCRs. In other words, S finds the subtree
         T=(V_T,E_T) of G that spans the set of nodes L such that

         cost(T)=sum cost(e) is minimised.
                   e in E_T

         We recognise this problem as the Steiner tree problem. Instead


Blazevic, Le Boudec                Expires 12/00                [Page 9]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


         of finding the exact solution, that is a NP-complete problem,
         we introduce a simple heuristic called Shortest Tunnel
         Heuristic (STH). The description of STH is given in the
         Appendix at the end of this document.

                                  ++++++++
                                 +        +
                                 + Area D +
                                 +        +
                                 +        +
                                  +      +
      ++++++++++                 +-+----+-+
     +          +                |DCR X4  |
     +           +               + ---+----+                   ++++++++++
     +            +            +      |     +               +            +
     +             +          +    (1)|      +             +             +
     +              +------+ +        |       + +--------+               +
     +              |DCR X1|+ <-----+ |  +---> +| DCR X3 |               +
     +              +------+ +   (2)| |  |(3) + +--------+               +
     +             +          +     | |  |   +            +              +
     +            +             +   | V  |  +               +   Area C   +
     +  Area A   +                +---+----+                 ++++++++++++
      +++++++++++                 |DCR X2  |
                                  +-+---+--+
                                  +        +
    At 1:                        +          +
    +-----+-----+---------+++    +          +
    |sa=X4|da=X2|opt=X1;X3|++    +          +
    +-----+-----+---------+++    +          +
                                 +  Area B  +
    At 2:                         +++++++++
    +-----+-----+++
    |sa=X2|da=X1|++
    +-----+-----+++       sa: source address
    At 3:                 da: destination address
    +-----+-----+++       opt: end-to-end option
    |sa=X2|da=X3|++       +++
    +-----+-----+++       |++ : encapsulated multicast data packet
                          +++



          Figure 2: Figure presents an example of inter-DCR multicast
         data distribution by using point-to-point tunnels. The source
         DCR is X4 and labelled DCRs are X1 and X3. X4 calculates the
         distribution tunnel tree to X1 and X3 by applying the STH
         heuristic presented in the Appendix. Assume that the result of
         STH gives the distribution tunnel tree consisting of edges
         X4-X2, X2-X1 and X2-X3. Then X4 sends the encapsulated
         multicast data packet to X2. In the end-to-end option field of
         the packet, a distribution list is contained. X2 sends two
         copies of multicast data: one to X1 and the other to X3. On


Blazevic, Le Boudec               Expires 12/00                [Page 10]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


         this figure are also presented packet formats at various points
         (points 1, 2 and 3) on the way from X4 to X1 and X3.

         The source DCR applies STH to determine the distribution tunnel
         tree from itself to the list of labelled DCRs for the multicast
         group. The source DCR puts inter-DCR distribution information
         in the form of an explicit distribution list in the end-to-end
         option field of the packet header. Under the assumption that
         there is a small number of receivers per multicast group, the
         number of labelled DCRs for a group is also small. Thus, an
         explicit distribution list that completely describes the
         distribution tunnel tree is not expected to be long.

         When a DCR receives a packet from another DCR, it reads from
         the distribution list whether it should make a copy of the
         multicast data and of the identities of the DCRs where it
         should send multicast data by tunneling. Labelled DCRs deliver
         data to local receivers in the corresponding area. An example
         that shows how multicast data is distributed among DCRs is
         presented in Figure 2.


3.6 How multicast data is forwarded from DCR to members of the group
inside its area

      A DCR receives encapsulated multicast data packets either from a
      source that is within its area, or from a DCR in another area. A
      DCR checks if it is labelled with the multicast group that
      corresponds to the received packet, i.e whether there are members
      of the multicast group in its area. If this is the case, a DCR
      forwards the multicast packet along the distribution subtree that
      is already established for the multicast group (as is described in
      Section 3.2).


4. DCM and cellular IP telephony

    In this section we present how DCM can be used to route packets to
   mobile hosts in cellular IP telephony (IPtel). We assume that the
   Session Initiation Protocol (SIP)[8] is used to establish, modify and
   terminate IPtel calls. Here we describe how DCM can be used in
   conjunction with SIP to support terminal mobility. Terminal mobility
   is the ability to maintain a communication when a host is moving from
   one location to another during the call.

   The owner of the mobile host is identified by its SIP URL address. A
   SIP server in the mobile host's home domain can be identified from
   this address. When the mobile host moves into the new domain it is
   assigned a temporary multicast address that it keeps as long as it
   stays in the same domain. How a multicast address is assigned to a
   mobile host is out of scope of this document. Then the mobile
   registers with a SIP server in its home domain in order to be found.


Blazevic, Le Boudec               Expires 12/00                [Page 11]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


   During the registration process, the mobile host sends to its home
   SIP server the anycast address of its current domain and its assigned
   multicast address. In each domain there are border routers that are
   configured with the domain anycast address and are responsible for
   accepting and forwarding packets for the mobile hosts that are in the
   domain. The domain anycast address is a reserved unicast address.
   Border routers configured with the anycast address recognise the
   anycast address as one of their logical interfaces. The routing of
   packets to the anycast address is done by standard unicast routing
   mechanisms.

   A caller that wants to establish a call with the mobile host has the
   knowledge of the mobile host's SIP URL address. Then, a caller
   contacts a SIP server in the mobile host's home domain for the mobile
   host's current location. A SIP server acts in the redirect mode and
   returns to the caller information about the anycast address of the
   mobile host's current domain and its assigned multicast address. A
   caller sends to the mobile host a SIP INVITE message. If the caller
   is also mobile, it informs the callee about its domain's anycast
   address and its assigned multicast address.

   When the sender to the mobile host and the mobile host are in the
   same domain, packets for the mobile host are destined to the mobile
   host's multicast address and are routed by DCM. This is done as
   explained in Section 3.

   If the sender and the mobile host are in different domains, multicast
   packets to the mobile host should first reach the domain where the
   mobile lies. We distinguish two cases to achieve this depending on
   the used version of the IP protocol.

   In the case of IPv6, a source sends a packet to the mobile host by
   using a loose source routing option. A source sets the destination
   field of the packet header to the multicast address assigned to the
   mobile host and the IPv6 routing header is set to the mobile host's
   domain router anycast address. A packet is routed to the nearest
   border router in the mobile host's domain that is configured with the
   anycast address. The next address to be visited is the multicast
   address assigned to the mobile host. DCM is used to route packets
   from the border router to the mobile host.

   In the case of IPv4, the sender sends multicast packets for the
   mobile host encapsulated (IP-in-IP) to the anycast address of the
   mobile host's current domain. The nearest border router that is
   configured with the anycast address decapsulates the multicast packet
   and, as in the case of IPv6, a packet is forwarded to the mobile host
   by using DCM.

   As explained in Section 3.1, for the mobile host's assigned multicast
   address, within each area, there exists a DCR that serves that
   multicast address. Those DCRs are responsible for forwarding packets
   to the mobile hosts within a domain. As said before, the DCRs run the


Blazevic, Le Boudec               Expires 12/00                [Page 12]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


   MDP control protocol and are members of a MDP control multicast group
   for exchanging MDP control information.

   A multicast router in the mobile host's cell initiates a joining the
   multicast group assigned to the mobile host. Typically this router
   coexists with the base station in the cell. As described in Section
   3.2 the JOIN message is propagated to the DCR inside the area that
   serves the mobile host's multicast address. Then, the DCR sends to
   the MDP control multicast group a MDP control message when the mobile
   host is registered.

                                         + + + + + + +
                                        +             +
                                         +   Area D  +
        + + + + + + + +                   +         +
      +                 +                  +       +
                         +                  +     +
      +                   +                +-+---+-+
         Area A            +               |DCR X4 |
      +                     +              +---+---+
                             +           +           +           + + + + + + +
      +            join       +         +             +        +             +
                  +----------> +-------+      (4)      +------+ (3) +------+ +
      +       (1)/             |DCR X1 | <-------------|DCR X3| <---|Sender| +
                /      (2)+--> +-------+               +------+     +------+ +
      +        /         /    +         +             +        +             +
             +-+-+  join/    +           +           +           +   Area C  +
      +      |BS1|     /    +              +-------+               + + + + + +
             +-+-+ +-+-+   +               |DCR X2 |
      +        ^   |BS2|  +                +-+---+-+
              _|   +---+ +                  +     +
      +       |         +                  +       +
              V        +                  +         +
      +     +-+-+     +                  +   Area B  +
            |MH |    +                    + + + + + +
      +     +-+-+   +
       + + + + + + +



    Figure 3: The mobile host (MH) is assigned multicast address M. Four
   DCRs, X1, X2, X3 and X4 serve M. Step (1): Base station BS1 sends a
   join message for M towards X1. X1 informs X2, X3 and X4 that it has a
   member for M. Step (2): Advance registration for M in a neighbouring
   cell is done by BS2. Step(3): The sender sends a packet to multicast
   group M. Step (4): The packet gets delivered through the backbone to
   X1. Step (5): X1 receives encapsulated multicast data packet. From X1
   data is forwarded to BS1 and BS2. MH receives data from BS1.

   In order to reduce packet latency and losses during a handover,
   advance registration can be performed. The goal is that when a mobile
   host moves to a new cell, the base station in the new cell should


Blazevic, Le Boudec               Expires 12/00                [Page 13]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


   already started receiving data for the mobile host. The mobile host
   continues to receive the data without disruption. There are several
   ways to perform this:

     - A base station that anticipates the arrival of a mobile host
       initiates joining the multicast address assigned to the mobile
       host. This is illustrated in one example in Figure 3. The
       mechanism by which the base station anticipates the arrival of
       the mobile host is out of the scope of this document.

     - In the case where bandwidth is not expensive on the wired
       network, all neighbouring base stations can start receiving data
       destined to a mobile host. This guarantees that there would be no
       latency and packet losses during a handover.

   A packet for the mobile host reaches all base stations that joined
   the multicast group assigned to the mobile host. At the same time the
   mobile host receives data only from a base station in its current
   cell. A base station that receives a packet on behalf of the mobile
   host that is not present in its cell can either discard a packet or
   buffer it for a certain interval of time (e.g. 10ms). Further
   research is needed to determine what is the best approach.

   Here we describe in more details how advance registration is
   performed. At its current cell, the mobile host receives data along
   the distribution subtree that is established for the mobile host's
   multicast address. This tree is rooted at the DCR and maintained with
   periodical sending of join messages. Now, suppose that the base
   station in the neighbouring cell anticipates arrival of the mobile
   host. It begins a joining process for the multicast group assigned to
   the mobile host. This process is terminated when a JOIN message
   reaches a router that is already on the distribution tree. When the
   cells are close to each other, joining is terminated at the lowest
   branching point in the distribution tree. This ensures that the
   neighbouring base station quickly becomes a part of the multicast
   distribution tree with low overhead. The neighbouring base station
   can start joining the multicast group assigned to the mobile host
   after the mobile host leaves its previous cell. Routers on the
   distribution tree keep forwarding information for a given time, even
   if the previous base station stops refreshing the tree because the
   mobile host leaves its cell. As before, if the base stations are
   close to each other, the multicast distribution tree for the new base
   station can be established in a short period of time that makes
   handover efficient.




5. Security Considerations

   Currently, DCM does not specify any special security measures. As in
   any routing protocols, however, there are a number of potential


Blazevic, Le Boudec               Expires 12/00                [Page 14]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


   security attacks possible. The use of authentication on all packets
   (i.e. IPSec authentication headers) is recommended to avoid such
   attacks.


6. Open Issues

   Since DCM is intra-domain routing protocol it is left for future work
   to examine interoperability of DCM with other inter-domain routing
   protocols. In this document we do not address the problems of using
   multicast routing to support end-to-end unicast communication. These
   problems are related to protocols such as: TCP, ICMP, IGMP, ARP. A
   simple solution to this problem could be to have a special range of
   unicast addresses that are routed as multicast addresses. In this
   way, packets destined to the mobile host are routed by using a
   multicast mechanism. Conversely, at the end systems, these packets
   are considered as unicast packets and standard unicast mechanisms are
   applied.


Appendix


Shortest Tunnel Heuristic (STH)

      STH consists of two phases. In the first phase a greedy tree is
      built by adding one by one the nodes that are closest to the tree
      under construction, and then removing unnecessary nodes. The
      second phase is further improving the tree established so far. The
      definitions of V, G, L and T are given in Section 3.5. STH is as
      follows:

      Phase 1: Build a greedy tree

        - Step 1: Begin with a subtree T of G consisting of the singe
          node S. k=1.

        - Step 2: if k=n then goto Step 4. n is the number of nodes in
          set V.
        - Step 3: Determine a node z_(k+1) in V, z_(k+1) not in T
          closest to T (ties are broken arbitrarily). Add the node
          z_(k+1) to T. k=k+1. Goto Step 2.
        - Step 4: Remove from T non-labelled DCRs of degree* 1 and
          degree 2** (one at a time).

        *  Degree of a node in a graph is the number of edges incident
          with a node

        **  A node of degree 2 is removed by its two edges being
          replaced by a single edge (tunnel) connecting the two nodes
          adjacent to the node being removed. The source DCR is never
          removed from a graph.


Blazevic, Le Boudec               Expires 12/00                [Page 15]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


      Phase 2: Improve a greedy tree

      STH can be further improved by two additional steps:

        - Step 5: Determine a minimum spanning tree for the subnetwork
          of G induced by the nodes in T (after the step 4).
        - Step 6: Remove from the minimum spanning tree non-labelled
          DCRs of degree 1 and 2 (one at a time). The resulting tree is
          the (suboptimal) solution.


7. References

     [1]  A. Ballardie. Core Based Trees (CBT) Multicast Routing
       Architecture. RFC 2201, September 1997.

     [2]  D. Estrin et.all. Protocol Independent Multicast-Sparse Mode
       (PIM-SM): Protocol Specification. RFC 2117, June 1997.

     [3]  Jayanth Mysore and Vaduvur Bharghavan. A New
       Multicasting-based Architecture for Internet Host Mobility. In
       The Third Annual ACM/IEEE International Conference on Mobile
       Computing and Networking (MobiCom'97).

     [4]  Liming Wei and Deborah Estrin. The Trade-offs of Multicast
       Trees and Algorithms. In  Proc.of the 1994 International
       Conference on Computer Communications and Networks, San
       Francisco, CA, USA, September 1994.

     [5]  David G. Thaler and Chinya V. Ravishankar. Distributed
       Center-Location Algorithms.  IEEE JSAC, 15(3), April 1997.

     [7]  Andras G. Valko. Cellular IP: A New Approach to Internet Host
       Mobility.  ACM SIGCOMM Computer Communicastion Review, January
       1999.

     [6]  C. Perkins. IP Mobility Support, Network Working Group. RFC
       2002, October 1996.

     [8]  M. Handley and H. Schulzrinne et. all. SIP: Session Initiation
       Protocol. RFC 2543, 1999.

     [9]  E. Wedlund and H. Schulzrinne. Mobility support using SIP. In
       Proc. of ACM/IEEE International Conference on Wireless and Mobile
       Multimedia (WoWMoM'99), Seattle, Washington, August 1999.

     [10]  Deborah Estrin, Mark Handley, Ahmed Helmy, Polly Huang, and
       David Thaler. A Dynamic Mechanism for Rendezvous-based Multicast
       Routing. In  Proc. of IEEE INFOCOM'99, New York, USA, March 1999.

     [11]  Vinod Valloppillil and Keith W. Ross. Cache Array Routing
       Protocol v1.0. INTERNET-DRAFT, 1998.


Blazevic, Le Boudec               Expires 12/00                [Page 16]


INTERNET-DRAFT       draft-blazevic-dcm-mobility-01.txt        June 2000


     [12]  D. G. Thaler and C. V. Ravishankar. Using Name-Based Mappings
       to Increase Hit Rates.  IEEE/ACM Transactions on Networking,
       6(1), February 1998.

     [13]  W. Fenner. Internet Group Management Protocol, Version 2. RFC
       2236, November 1997.




8. Author's address

   Ljubica Blazevic
   Jean-Yves Le Boudec
   Institute for computer Communications and Applications
   Swiss Federal Institute of Technology (EPFL)
   CH-1015 Lausanne
   Switzerland
   email: Ljubica.Blazevic, leboudec@epfl.ch



































Blazevic, Le Boudec               Expires 12/00                [Page 17]


Html markup produced by rfcmarkup 1.128b, available from https://tools.ietf.org/tools/rfcmarkup/