Classless Inter-Domain Routing

Classless Inter-Domain Routing (CIDR ˈsaɪdər,_ˈsɪ-) is a method for allocating IP addresses and for IP routing. The Internet Engineering Task Force introduced CIDR in 1993 to replace the previous classful network addressing architecture on the Internet. Its goal was to slow the growth of routing tables on routers across the Internet, and to help slow the rapid exhaustion of IPv4 addresses. IP addresses are described as consisting of two groups of bits in the address: the most significant bits are the network prefix, which identifies a whole network or subnet, and the least significant set forms the host identifier, which specifies a particular interface of a host on that network. This division is used as the basis of traffic routing between IP networks and for address allocation policies. Whereas classful network design for IPv4 sized the network prefix as one or more 8-bit groups, resulting in the blocks of Class A, B, or C addresses, under CIDR address space is allocated to Interne

Scalable routing protocols with applications to mobility

Ljubica Blazevic

In this thesis we study two routing problems related to mobility. The first problem concerns scalable multicast routing when there is a large number of multicast groups with a small number of receivers. Existing dense and sparse mode routing protocols have the following problems when the number of groups is large, but the groups are small: (1) high overhead in control traffic (dense mode), (2) poor utilization of backbone links and (3) complexity of management of single core routers (sparse mode). Our solution to this problem is the Distributed Core Multicast (DCM) routing protocol. DCM is an extension of the core-based tree approach and its architecture is based on several core routers per multicast groups. We explain the objectives achieved with DCM: (1) avoiding state information in backbone routers, (2) avoiding triangular routing across expensive backbone links, (3) scaling well with the number of multicast groups. DCM can be applied to support host micromobility in a large single Internet domain network, where every mobile host is assigned a multicast address in a domain it visits. The advantages of the multicasting-based approach for supporting host mobility are low latency and minimal disruption during handover. The second problem studied in this thesis concerns scalable routing in a large scale mobile ad hoc network. Ad hoc networks have gained increasing popularity in recent years because of their ease of deployment. No wired base station or infrastructure is needed, and mobile nodes communicate with each other using multi-hop wireless links. In ad hoc networks, routing protocols are challenged by the establishment of and the maintenance of multihop routes in the face of mobility, bandwidth limitation and power constraints. Routing protocols that rely on state concerning all links on the network, or all links on a route between a source and a destination result in poor scaling properties in larger mobile ad hoc networks. Position-based routing protocols are better suited for large mobile ad hoc networks. These protocols use the positions of nearby nodes and of packet's destination to make the packet forwarding decisions. We present a scalable routing protocol for a large mobile ad hoc network that is called terminode network. We call the nodes terminodes because they act as network nodes and terminals at the same time. Our routing scheme is a combination of two protocols called Terminode Local Routing (TLR) and Terminode Remote Routing (TRR). TRR is activated when the destination is remote and it uses the location of the destination obtained either via location management or by location tracking. TLR acts when the packet gets close to the destination and it uses routing tables that are built by nodes for close terminodes. The use of TRR results in a scalable solution that reduces dependence on the intermediate systems, while TLR allows to increase the probability of reaching the destination, even when it has moved considerably from the location that was known at the source. We use simulations to demonstrate terminode routing's scalability in different sized mobile ad hoc networks.

EPFL2002

Distributed Core Multicast (DCM): a routing protocol for many groups with few receivers

Ljubica Blazevic, Jean-Yves Le Boudec

We present 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. It uses several core routers, called Distributed Core Routers (DCRs) and a special control protocol among 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 the Internet, where each mobile 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.

1999

Scalable routing protocols with applications to mobility

Ljubica Blazevic

EPFL2002