INTERNET-DRAFT J-J Pansiot, D. Grad, November 1998 T. Noel, Expires May 1999 A. Alloui LSIIT Strasbourg Logical addressing and routing for multicasting(LAR) Status of this Memo This document is an Internet Draft. 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 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 a "work in progress". Abstract This document describes an architecture based on two levels of addressing. A logical addressing level is used to identify logical objects independently of their current IP address, such as multicast groups or mobile hosts. This schema is then used to define in a unified way mechanisms for inter-domain multicasting and mobility. 1. Introduction In this draft we present an architecture (called LAR for Logical Addressing and Routing) for efficient multicasting and mobility. This architecture is based on two types of addresses: - Routing addresses (such as current IP unicast addresses) are used in the routing process. These addresses may change, reflecting changes in routing (mobility, renumbering) - Logical addresses are used to uniquely identify hosts or other objects. These addresses must not change when routing changes. For example multicast addresses may be considered as identifiers. We observe that in some situations many protocols in the Internet use packets containing two levels of addressing. This can be illustrated by two examples (for the time being, we consider only Draft LAR Novembre 1998 destination addresses): - In PIM-SM [RFC2362] or CBT [RFC2189], packets sent by a source which is not part of the multicast tree are encapsulated towards the RP or Core: the outer header contains a routing address (of the RP) while the inner header contains a logical address (a multicast address). - In Mobile IP [RFC2002], when a packet is forwarded to a mobile host from its Home Agent, it contains a routing header. The outer header contains a routing address (the current address of the mobile), while the inner header (the routing header) contains the home address of the mobile. This last address may be considered as an identifier, since it should not change over time when routing changes. In both cases, the outer address is a routing address and the inner one an identifier. Our architecture is a generalization of this idea. It allows some simplification of multicast protocols, in particular in the case of sparse and inter-domain groups, and unifies mechanisms used for multicasting and mobility. Our architecture considers logical objects, each having a logical address (called a LAR address). In the following we call a LAR host (respectively a LAR router) a host (resp. a router) implementing LAR. A node is either a host or a router. The basic logical object is a logical node. For example a mobile host has a LAR address, independently of its physical location in the network. Other logical objects (e.g. groups) have logical addresses derived from host addresses, greatly simplifying multicast address allocation. LAR packets contain a logical header, containing source and destination logical addresses, in addition to the usual header containing source and destination routing addresses. The LAR destination address corresponds to the final destination while the routing destination address may correspond to an intermediate node, for example a multicast router that duplicates packets sent to a group. Routing addresses may be changed from a logical hop to the next, much in the same way as MAC addresses are changed when going through a router. A node maintains a LAR cache table, similar to the ARP cache, containing the current correspondence between routing addresses and LAR addresses of their correspondents. In the case of multicasting, a node maintains a Logical Routing table that associates a LAR group address to the list of LAR addresses of neighbors in the multicasting tree. This table contains an entry for a group only if the node has an active role in the group (it duplicates packets). Hosts wishing to join a group send their join request to the group manager. This group manager, possibly after some security checking, forwards the request down the tree towards the new member. Advantages of this architecture: - Since join requests travel downstream from root to members, Expires May 1999 [Page 2] Draft LAR Novembre 1998 routers don't need to know in advance root (or RP, core) addresses: there is no need for a bootstrap router mechanism. - Since LAR multicast addresses are just identifiers derived from host LAR addresses, there is no need for a multicast address allocation protocol [MASC]. - For a given group, only routers that duplicate packets (i.e. routers with at least 3 interfaces in the multicast tree) must maintain information for that group. This implies a big saving in state, especially for sparse wide area groups. In particular it is possible for a multicast tree to get through whole transit domains without any state information maintained in these domains. - Since a multicast router knows its neighbours (in a given multicast tree) by their logical addresses, a change of unicast route between two neighbors does not break the tree as long as another unicast route exists. In particular the failure of a single link interrupts a multicast communication only the time for the unicast routing protocol to find another route, without any action at the LAR multicast routing level (see section 6). - Since nodes maintain in a cache the correspondence between LAR addresses and routing addresses, mobility mechanisms are just updates of this cache. This works not only for unicast (such as in Mobile IP) but also for multicast. When a mobile moves, it just needs to update the table of its neighbours in multicast trees it belongs to. There is no need to remove a tree branch at the former location and add a tree branch at the new location. The duration of traffic disruption is about the same as in the unicast case, namely the time of a binding update. - The LAR cache hides routing addresses from applications: An application need not know of events such as renumbering, or change of interface for a multihomed host. Transport or application level connections are not broken by these events. - LAR multicast trees can be constructed even if some intermediate routers (or even whole routing domains) do not implement LAR, or do not wish to duplicate packets for a given group. At worse, the multicast tree won’t be optimal. In particular, it is not mandatory for a group member to be directly connected to a LAR router. - In the LAR architecture, it is possible to define a group (a set of hosts sharing some goals) and subgroups (subset of hosts sharing an application at a given time). Some features of this architecture are similar to the Simple Multicast Proposal [SIMPLE], although mechanisms are different. Note that this draft is not the specification of a protocol, but the general description of an architecture. Section 2 deals with addressing and naming, section 3 with communication management, section 4 with logical routing, section 5 with mobility, section 6 with robustness, section 7 with scalability and section 8 with security. Expires May 1999 [Page 3] Draft LAR Novembre 1998 2. LAR addressing and naming In this architecture, we propose the addition of a new addressing space in addition to the usual network addressing. It allows a unique and simplified framework for multicasting and mobility. 2.1. Addressing The basic model is as follows: any logical object has a logical address that is globally unique and non-ambiguous in the Internet. There are primarily two types of logical objects: logical hosts and communications. The basic object that can be addressed in our architecture is a host implementing LAR. Such a host acquires an individual logical address by the same mechanisms it acquires a fully qualified domain name. The main differences between network addresses and LAR addresses are the following: - A host may have only one LAR address even if it is multihomed. This is because applications usually don't care about the actual interface used, and should not be disrupted when the interface used changes. Note that it is possible for a physical host to have several logical addresses, if it is hosting several logical hosts. This could be the case of several web servers with different names sharing the same host. - A LAR address is independent of routing information. Therefore it remains unchanged when a host changes its physical location (mobility) its Internet provider (renumbering) or the interface used (multihoming). Therefore host LAR addresses are logical host identifiers and one may compare them to other identifiers such as MAC addresses or EUI- 64 identifiers except that: - a LAR address identifies a host, not an interface - a LAR address is independent of the hardware (it remains unchanged even if the actual machine or interface is changed) - one can easily retrieve the name of a host from its LAR address (see section 2.2) The other type of logical object with a logical address is a communication. Indeed, a communication LAR address identifies a communication implying N partners (N>=2). If N=2, the communication is point-to-point, and the use of logical addressing provides stable communications with mobiles and may offer a solution for letting TCP connections survive (network) addresses changes problem [HUITEMA]. The case N>2 represents a group communication and this type of LAR addresses is similar to class D IP addresses. A group, in our architecture, has a manager, which deals with the control of the group (see section 3 for more details). Several applications may be run simultaneously in the group, possibly involving subgroups of members. Indeed, members of a same group do not necessarily all have Expires May 1999 [Page 4] Draft LAR Novembre 1998 the same needs nor the same resources. For example, some will ask for a video stream whereas others simply wish to dialogue using a white board application. The group manager can decide to create two communication instances (two trees) with two different communication (logical) addresses, allowing each member to take part in one or the other (or both) communication(s). One may have several trees in the same group to deal with applications having different requirements, for example a shared centered tree for a whiteboard, and several source rooted shortest path trees for video sources. Moreover filtering may be used to deliver data to only interested members of the group: a packet sent to a subgroup travels along a tree but may be filtered at some intermediate nodes. That is only one tree has to be maintained for several applications with distinct subsets of receivers. On the other hand, there is a particular shared tree connecting all group members, called the control tree. It offers a support for the exchange of control messages inside the whole group. It can be used in particular by the group manager to advertise the creation of new instances, and their logical addresses, and the launching of new applications. A group LAR address is constructed by adding a suffix to the logical address of the group's creator. Thus, group address allocation may be achieved in a simple and distributed way without the need for a multicast address allocation protocol. In the same way, the logical address of a communication instance is derived from the address of the group by adding a suffix. 2.2. Naming, addressing and their relationship In many cases it is helpful for logical objects to have a name for human use. We define an addressing schema and a name service providing the name to LAR address and LAR address to name mappings in a simple way. This service may be achieved using an extension to the DNS, by adding a new record type and using dynamic updates. Addresses and names used in LAR are built in the same hierarchical way: host (creator) > group > instance (tree). One can query the name service with the (LAR) name of a host to get its logical address and its network address, and similarly a request with a group (LAR) name will provide the logical address of the group as well as the name of its manager. Unlike the current Domain Name System, where the name and address hierarchies are completely independent, we propose an addressing schema in which logical addresses and names reflect the same hierarchy. This is possible only because LAR addresses are independent of routing. A host LAR address is a coding of a Fully Qualified Domain Name. Each domain gives a unique number to its child domain. The “human” representation of LAR addresses will be dotted decimal. For example, if top domain fr is given number 15 among all top domains, domain u-strasbg is given number 155 inside domain fr, and host clarinet is given number 2654 inside domain Expires May 1999 [Page 5] Draft LAR Novembre 1998 u-strasbg.fr, we have: clarinet.u-strasbg.fr <-> 15.155.2654 This notation is very similar to the designation of objects in a SNMP MIB [RFC 1155]. With this notation, we don't need to create a new hierarchy of Domain Name Servers. The address to name table can be automatically constructed from the name to address table. In the same way, one can easily add a level of hierarchy to the logical names, taking into account that groups created by a host add a level to the tree structure. In our example if host clarinet is responsible for the creation of a group called jazz with (local) number 3 then one has the mapping: jazz.clarinet.u-strasbg.fr <-> 15.155.2654.3 As far as encoding is concerned, we may use the compact encoding used in SNMP for object identifier. This is possible only if this variable length encoding fits into a fixed size LAR address field. We think this is possible in the case of IPv6 addresses. Indeed with an SNMP-like encoding, we expect that each host can be assigned a LAR address using at most ten bytes. Therefore we suggest that LAR addresses be taken inside the IPv6 address space, with a specific prefix. If we assume for example a 12 bits prefix LAR_PREFIX, a 4-bit address length field, a LAR address will be of the form: LAR_PREFIX.ADDRESS_LENGTH.LAR_HOST.SELECTORS coded with 16 bytes. The LAR_HOST part should be in most cases less than 10 bytes, leaving 4 bytes for selectors. This leaves for example the possibility for one host to create 2^16 groups, each one with 2^16 instances. Note that with this choice current applications should not be aware of the difference between LAR addresses and IPv6 addresses, and should be able to use both types of addresses. 3. Communication manager 3.1. Communication manager functionalities Any LAR host has a Communication Manager. This LAR entity manages LAR communications initiated or used by this host. Indeed, the creator of a group can define a certain number of parameters associated with this group. For example, it can authorize only certain hosts to join. It can also define a set of applications that can operate above the LAR communication. It has the possibility also of defining some security rules for adhesion. This functionality offers some security, since requests to join a LAR communication must go through the communication manager of the group creator (or its delegated manager). Joining a LAR group communication does not depend only on the single initiative of the new candidate, but also on the management rules used for this particular group communication. Expires May 1999 [Page 6] Draft LAR Novembre 1998 The Communication manager of a LAR host memorizes the characteristics of the communications it belongs to. At the time of its initialization, each local manager must have at least the following configuration parameters: - Its logical address, - Its logical name, - LAR host addresses for which it is the delegated manager. If an application wishes to join a group communication, it asks its (local) manager to make the steps of joining. The manager must get in touch with the manager of the group. Thereafter, it has the responsibility to inform and communicate the LAR communication address to the application. The manager memorizes for each group for which it is responsible, the characteristics of the group and available applications. It deals with LAR address allocation, it queries and updates the domain name service (DNS) for logical names and addresses, it receives and processes join requests. We describe these mechanisms by detailing the various group operations in the LAR architecture: creating, joining and leaving a group. 3.2. Group naming A group communication is identified by a logical hierarchical name, similar to a DNS (Domain Name Service) name. For instance, « jazz.clarinet.u-strasbg.fr » could represent a conference organised by some user of host clarinet, whose goal could be to multicast jazz songs all over the internet. The association between a group name and the corresponding unique LAR address can be performed by a DNS. This DNS must support dynamic updates (RFC 2136) because groups may be created dynamically. To join a LAR communication, the group LAR address and the name of the group manager are needed. Thus, with the name of the group communication are associated the LAR group address and the LAR name of the manager. In most cases, we expect that the manager name is the name of the group creator, and is a prefix of the group name. In the previous example, the communication manager of jazz.clarinet.u- strasbg.fr is the hostname clarinet.u-strasbg.fr. But in some cases, the communication manager of a group communication may be located on another host. 3.3. Group creation Let us take the example of a host H named NAME_H wishing to create a group named PARTIAL_NAME. The host transmits to its local manager a group creation message that specifies this name. Upon receipt of this message, the manager gives a full name and address to the group. It prepends the partial name provided by the host’s application to its name (i.e.: NAME_G = PARTIAL_NAME.NAME_H), then it creates a LAR address identifying the group, by addition of a selector to its own logical address (i.e. @LG = @LH.SEL). The selector uniquely identifies this group among all groups created by Expires May 1999 [Page 7] Draft LAR Novembre 1998 this manager. Then the manager dynamically updates the DNS which associates the group name (NAME_G) and its LAR communication address (@LG) as well as the name of the group manager (in this case NAME_H). Finally, the manager triggers the creation of a multicast tree reduced to a single node H if H is the root of the tree. The logical routing table for H associates the group address with its own LAR address (i.e. @LG -> @LH). . If the root R of the tree is not H, the tree is reduced to an edge joining H to R, and the logical routing table of H contains @LG -> @LH, @LR. When a host creates a group, it has the possibility to define some rules for group management. For example, it can authorize or not hosts to send data to the group without being a member (open group). It can also ask the group manager to authorize only certain hosts to join the communication. As seen above, when an application wants to create a group, it asks its local manager to manage it. However it is possible for the local manager to delegate this responsibility to another (remote) manager. For example, this could be the case for a mobile host delegating management to a fixed host. 3.4. Joining a group We suppose that host H learns a group name by any mean independent of our architecture, for example www, session directory, electronic mail, or news, and H wishes to join this group. The host queries the DNS, which returns the LAR group address (noted @LG), and the LAR manager address, noted @LM. The host can then send a join request to the group manager. Upon receipt of the request, the manager accepts or not H as a new member of the group. In a positive case the manager triggers the insertion of H in the multicast tree associated to the group. Finally, host H receives the LAR address of its neighbour in the tree, and stores it in the logical routing table entry corresponding to this group. 3.5. Leaving a group A group member may announce its leaving to its neighbor with a LAR_LEAVE message. The neighbour node may also detect that the host as left (or failed) if it has not received a LAR_HELLO message for a specified time. 3.6 Tree instances Once a group is created, with its associated bi-directional tree connecting all members called the control tree, one or several applications may be launched using this tree. If an application has Expires May 1999 [Page 8] Draft LAR Novembre 1998 a need for a special kind of tree (for example a source rooted tree for a video stream), it may ask the manager to trigger the creation of a new communication instance (with a new address derived from the group address), corresponding to a new tree. The creation of this new instance is advertised via the control tree, and other members may join this new tree. 4. Logical Routing 4.1. Reduced trees and Logical forwarding A LAR tree is a tree whose vertices are nodes implementing a LAR entity, and whose edges are (network) routes between these nodes. In the common case of unicast communications, a LAR tree is usually only a single edge connecting two hosts. In the case of multicast communications, a LAR tree is usually composed of several nodes, including end nodes of degree one corresponding to sources or receivers, and interior nodes with degree at least two, that duplicate and forward packets to their neighbours. A packet is forwarded from one node to all end nodes of the LAR tree corresponding to the LAR destination address. In the case of multicast, LAR addresses can be seen as tree identifiers. Note that a LAR neighbour is not necessarily a direct neighbour at the network level. Instead, one may construct reduced multicast trees, where nodes have a duplication role: basically they have degree at least 3. Therefore an edge of a reduced multicast tree is in fact a route at the network level. Intermediate routers along logical tree edges forward packets based on the network level address as usual, and don’t even need to implement a LAR entity. In most unicast cases, only LAR entities at endpoints are concerned. In a LAR node N, given a LAR destination address, the forwarding process consists in determining neighbours in the LAR tree and then sending a copy of the packet to all the neighbours except the sending one. Therefore the network header must contain the network address of LAR node N, in order for the receiving LAR node to know which incoming logical edge was used. 4.2. Logical Routing Data Structures One role of the LAR entity is to dynamically map LAR addresses and network addresses, in presence of network-level changes. This is done by maintaining a LAR cache table. For each LAR node address in use, this table contains an entry with the current correspondence between the node LAR address and a usable network address. In addition, this entry may contain a list of other network addresses of the same node, for example for routers or multihomed hosts. This table is updated when network addresses change (mobility, renumbering, …). Expires May 1999 [Page 9] Draft LAR Novembre 1998 A LAR routing protocol is in charge of constructing and maintaining a LAR tree called a reduced tree. At each node, local tree information is maintained in the LAR logical routing table. This table contains the current correspondence between a LAR communication address and the list of neighbour LAR addresses to which a packet must be sent. In the case of a multicast LAR address, this is the list of adjacent nodes in the multicast tree. This table is the local view of a LAR tree. A flag UNI_TREE is encoded in the address. If this flag is set, data may only flow from the root of the tree, and routers must remember which edge is towards the root. If this flag is not set, the tree is bi-directional. Data arriving by any edge is propagated to all other edges. The initial tree for a group (the control tree) is always bi- directional to allow multipoint to multipoint communication. Another problem with multicast routing is the possibility for sources outside a group to send data to the group (such a group is called open). We propose the following mechanism: when a LAR communication is created its creator decides if it is open or not. A corresponding flag OPEN_TREE is encoded in the address. A LAR router may or not accept to be part of a tree whose address has the OPEN_TREE flag set. When a router receives a multicast packet from a node which is not a neighbour in the LAR tree, the packet is forwarded to all neighbours if the tree is open, otherwise it is discarded. In the former case, an OUTSIDE flag is set in the header to warn all members that the sender is not a member of the group. Note for Ipv6: We could define a hop by hop option such that a packet sent toward the root of the tree by an outside source is intercepted by the first router which is part of the open tree, and then propagated along the bi-directional tree. 4.3. Filtering When a new application is launched inside a group or inside a specific communication instance, not all group members may be willing or capable to run this application, introducing the notion of a subgroup. A packet sent to a subgroup travels along the tree corresponding to the group (or instance) but may be filtered at some intermediate nodes. In order to do this, a logical routing table entry may contain a MASK field for each neighbour and the logical packet header includes a SUBGROUP field. Only packets whose SUBGROUP field matches the MASK value (A logical AND of this two values is not all zeroes) are forwarded onto corresponding logical edges. Mask values are transmitted from receivers toward the root, using the tree maintenance messages (LAR_HELLO). They are OR’ed at intermediate nodes. Expires May 1999 [Page 10] Draft LAR Novembre 1998 Note that subgroup filtering is a priori restricted to unidirectional trees, in order to avoid remembering one mask for each pair (incoming edge, outgoing edge). 4.4. Sending to a logical object A LAR packet sent by a node S to a logical object D (tree or neighbor in case of unicast) is encapsulated in a Network level packet. At the Network level, source and destination addresses are Network addresses of the current logical edge (@NA as sender and @NB as neighbour if we consider logical edge A B). At the LAR level, source and destination addresses are logical addresses of the initial sender @LS and of the final destination @LD (tree or neighbor). | Network header | Logical header | M s g +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | @NA | @NB |...| @LS | @LD |...|. . . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The receiving node B, following a logical routing table lookup, duplicates the packet to each tree neighbour, encapsulating the unchanged logical header in each Network packet (@NB as source and @NN for each neighbour). 5. Mobility The LAR architecture is well suited for communications where correspondents must be identified logically (i.e.. independently of their current Network address), like mobile hosts. Indeed, LAR hosts use logical addresses as identifiers. In particular, applications or transport level connections may use these identifiers instead of network addresses. This can be done transparently if LAR addresses and network addresses share the same addressing space. This is possible for example with Ipv6 addresses. The binding between the Network addresses and the LAR address of a host is done through the LAR cache table. It associates the logical identifier with the list of current network addresses of a LAR host. When a mobile node moves and acquires a new network address, it continues to use its LAR address as an identifier of the communication. It only updates the LAR cache table of its correspondents by sending its new network address, similarly to the binding update of Mobile IP. However, contrary to Mobile IP, this mechanism works in the same way for multicasting: the mobile host updates the LAR cache table of its neighbours in LAR trees. There is no need to tunnel data between the Home Agent and the Mobile or to have the mobile make a new join at its new location. This relatively simple mechanism allows a transparent use of the mobile hosts in the LAR framework. Expires May 1999 [Page 11] Draft LAR Novembre 1998 6. Robustness In this section we consider problems that may arise from failures in the network. 6.1 Link failure The most common failure is a network link failure. In our architecture, this would lead to the following scenario: 1) A unicast route used by a logical edge (say from A to D) becomes unavailable, 2) the unicast routing process detects this problem and computes a new unicast route, 3) two cases may arise whether or not the last hop of the unicast route changes, - If the new route has the same last hop than the old one in both directions (for example route A-B-C-D becomes A-B-E-C-D after the failure of link B-C), there is no change at all in the LAR tree, and multicast traffic is disrupted only while unicast routing converges, - If the new route has a new last hop (for example route A-B-C-D becomes route A-B-E-D after the failure of link C-D), LAR packets sent along the logical edge A-D will be sent to the network address of D corresponding to the failed link. In this case it is possible that a NET (or HOST) UNREACHABLE message is received. The LAR routing process of A may then update the LAR cache table entry for host D, by removing the unavailable network address from the list and replacing it by another one. This is possible since a LAR cache entry contains the list of all known network addresses for a node. Again the LAR tree itself is not changed, and multicasting is disrupted while unicast routing converges plus the time to update the cache entry. 6.2 Node failure The failure of a node, which is not a node of the LAR tree, but is an intermediate router along a logical edge is very similar to the failure of a link, and is solved in the same way. More generally, most changes in the unicast routing that do not affect the reachability of LAR nodes of a tree will be considered in the same way. A more serious problem is the failure of a LAR tree node. Note that in the classical model for multicasting, all nodes forwarding data packets for a group are part of the multicast tree, whereas in our architecture, only a fraction of these nodes are LAR tree nodes. A tree maintenance protocol is used: tree nodes send periodically a HELLO message to their father in the tree (with an acknowledgement from the father). The absence of HELLO for a specified duration indicates that the downstream node has failed. If the specified duration is greater than the unicast routing protocol convergence Expires May 1999 [Page 12] Draft LAR Novembre 1998 delay, it really means that the node is dead or the network is partitioned. In this case the failed node is removed from the logical routing table. Symmetrically, sons of the failed node detect this failure. They may flush the entire subtree. Another possibility would be for these sons to ask via the group manager to be grafted to the tree. This implies that routers must keep track of group managers. This solution would be more scalable for very large groups and failures close to the root. The root failure is an even more important issue. If we consider that the group manager did not failed, or that several redundant managers have been set up, a possible solution is as follows: the group manager detects the root failure and chooses a new root. When sons of the failed root detect this failure, they ask the manager to be grafted back to the tree. The manager sends this request to the new root, similarly to the failure of any LAR node. 6.3 Tree reshaping In the LAR architecture, many changes in the underlying network (change in unicast routing, renumbering, move of a mobile host) are taken into account by updating the LAR cache table. Network routes corresponding to a LAR edge change but the logical tree remains the same. In many cases this will lead to a non-optimal tree. In particular, it is possible that at a given time, two edges from a node share the same first network hop. The LAR routing protocol will be in charge to detect this kind of situation, and to reshape the tree, by adding and/or removing a LAR node. Example: for a given tree, assume node A has 3 LAR neighbours B, C and D. The unicast route from A to B is A-E-B, and the unicast route from A to C is A-F-C. These two routes are disjoint. Assume now that node E fails. The unicast routing will replace route A-E-B by say A- F-G-B. The LAR tree is again operational, but LAR edges AB and AC start with the same first hop F. In this case the LAR routing protocol will detect this, and split edge A-C into two edges A-E and E-C where E is a new LAR node in the tree. Then edge A-B will be replaced by edge E-B. 7. Scalability issues Inter Domain multicasting brings several scalability problems. 7.1. Tree state in routers State to be maintained in a router which is part of a multicast tree is similar to other sparse mode protocols 5CBT, PIM-SM). However, less routers will be involved in a given tree, especially for very sparse groups. For example a group consisting of 3 members in one site in California and 3 other members in another site in France, might involve only two routers, one on each site, whereas current protocols would involve at least a dozen routers along the route between the two sites, including routers in Internet backbones. Note that in our architecture, if a multicast tree connects N different LANS, it involves at most N-1 routers. Expires May 1999 [Page 13] Draft LAR Novembre 1998 Obviously, if multicast becomes widely used in the internet, routers may still have a huge number of trees to remember, and tree aggregation is a hard problem. The notion of filtering and subgroups is a first step to avoid the creation of many similar trees. 7.2. Address allocation, root advertisement. Our architecture does not need a specific address allocation protocol (at least if used with Ipv6), nor protocols to advertise root (Core, RP) for trees. This saves both state in routers and bandwidth. The root of a tree is chosen by its communication manager and may be replaced by the same manager. The manager may be dynamically retrieved from the group address via the DNS. Therefore several problems with multicasting are handled by communication managers, not routers. A significant part of the load due to a group is supported by the group manager, which seems more scalable. 7.3. Very large groups Our architecture was more specifically designed for sparse groups. However it could be extended to dense groups by using LAR over dense mode multicast in dense clouds. Another problem with very large groups is the reconnection of whole sub-trees when a node fails. Our notion of logical edge should simplify the grafting of a sub-tree back to a tree. 8. Security Since LAR addresses never change, both when travelling inside the network (no translation) and with time (mobiles keep their LAR address), an authentication header should be based on the LAR extension header. The network header will change with time (mobility) and while the packet gets through LAR nodes. Since a LAR address remains unchanged across network renumbering, and the name of the host can be retrieved from the address, it is also a good key for accounting. Note that a packet with a given LAR source address may come from anywhere, since this address is independent of physical location (easy spoofing). Therefore when security is a concern, the authentication header must be used. 9. Further Work Part of the LAR architecture has been implemented using Ipv6, on FreeBSD, both for multicasting and mobility. The LAR header is implemented as a Ipv6 destination option. Since we have taken LAR addresses as a subset of Ipv6 addresses, applications may use LAR without much change. The LAR logical routing table and the cache table are implemented in the kernel. Obviously many things remain to be done. Among them: - study how to deal with broadcast medium Expires May 1999 [Page 14] Draft LAR Novembre 1998 - give a precise specification of the LAR routing protocol to construct a LAR tree - study how LAR could interact with other multicast protocols. Note LAR could be run in parallel with other multicast protocol since it uses a different encapsulation. 10. Author’s address Jean-Jacques Pansiot, Dominique Grad, Thomas Noel, Abdelghani Alloui LSIIT, Louis Pasteur University Boulevard Sebastien Brant 67400 ILLKIRCH FRANCE Email: {pansiot, grad, noel, alloui}@dpt-info.u-strasbg.fr 11. References [BGMP] Border Gateway Multicast Protocol (BGMP):Protocol Specification . D. Thaler, D. Estrin, D. Meyer. August 1998. [HUITEMA] C; Huitema Multi-homed TCP, internet-draft, May 1995. [MALLOC] The Multicast Address-Set Claim (MASC) Protocol, , D Estrin et al. August 1998. [RFC 1157] Simple Network Management Protocol (SNMP). J.D. Case, M. Fedor, M.L. Schoffstall, C. Davin. May-01-1990. [RFC 2002] IP Mobility Support. C. Perkins. October 1996. [RFC 2137] Secure Domain Name System Dynamic Update, D. Eastlake, April 1997 [RFC 2189] Core Based Trees (CBT version 2) Multicast Routing. A. Ballardie. September 1997 [RFC 2201] Core Based Trees (CBT) Multicast Routing Architecture. A. Ballardie. September 1997. [RFC 2362] Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification. D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. Handley, V. Jacobson, C. Liu, P. Sharma, L. Wei. June 1998. [SIMPLE] A Design for Simple, Low-Overhead Multicast, , R.Perlman, C-Y Lee, A. Ballardie, J. Crowcroft, August 1998.