Multicast Routing in Datagram Internetworks and Extended LANs April 27, 2009

This paper talks about extending multicast beyond a single LAN. At the time of writing (1990) multicast was feasible in LANs, but not across LANs. In order to support multicast across multiple LANs, the paper offers extensions to three common routing algorithms for unicast:

1. Single-Spanning Tree Multicast Routing: Existing bridges of the day would forward broadcast and multicast packets to every segment of the extended LAN. To save bandwidth and processing time, the authors suggest one multicast member from each LAN to periodically send a membership-report to all bridges. When a bridge receives a membership-report from a multicast group G, it remembers which direction the packet arrived from. Any subsequent packets destined to group G would then be only forwarded along the direction of that group. For example if bridge B receives a membership packet from LAN C destined to LAN D, with multicast group G, then the bridge learns to forward packets of G from LAN C to LAN D, but not vice versa nor to any other LAN. This saves bandwidth that would otherwise be wasted by forwarding multicast packets along all segments connected to the bridge
2. Distance Vector Multicast Routing: by sending routing packets, routers maintain distance vectors to all other routers, thus enabling them to compute shortest-path routes to all other nodes in the network. The authors build on top of several existing unicast algorithms. Using Reverse Path Flooding (RPF), a router forwards a broadcast message from source S to all other links, iff the packet arrived from the shortest path from the router to S. Reverse Path Broadcasting (RPB) modified RPF so that packets are not forwarded to the parent router — router with minimum distance to S. This provides shortest-path broadcasting while avoiding duplicate messages. Truncated RPB (TRPB) builds on top of this but deletes child links that no router uses to reach the multicast sender. Finally, Reverse Path Multicasting (RPM) narrows the broadcast tree further by receiving non-membership messages from routers that are not connected to the multicast-group, and by removing these non-members from the multicast spanning tree.
3. Link-state Multicast Routing: Using this approach, each router monitors its attached links. Upon detecting a change in a link state, all routers attached to that link broadcast the change to every other router. By doing so, each router learns the complete topology of the internetwork, and can find shortest paths to any node in the network using Dijkstra’s algorithm. To extend this algorithm to support shortest-path multicast, the routers would consider creation of new groups or deletion of old groups as a state change, and broadcast this multicast-group-change to all other routers. Like the algorithms above, the hosts periodically send membership-reports to the routers in order to maintain multicast membership information.

Most glaring problem: The paper proposes many algorithms and ideas, but there is no implementation. The authors speculate the efficiency of their algorithm without providing any experimental results or simulations. Also the algorithms presented are non-trivial, and would require extra router memory, as well as increased processing. It is my impression that there might be too much overhead using the distance-vector algorithms. The link-state algorithm seems very simple and efficient but might not be practical across LANs because the state change is broadcast to the entire network.

Future research: it would be interesting to extend the distance-vector algorithms to use source-routing (I am not aware whether they do this or not). By doing so, a router who finds a shortest path for the multicast packet could specify this path and relieve the other routers from the burden of calculating shortest paths again.

Internet Indirection Infrastructure April 16, 2009

Three Important Things:

• The motivating observation by the authors is that the demand for additional internet abstractions is out there, and the current IP layer cannot provide things such as multicast, anycast, and mobility in a scalable way. Taking the overlay network approach to this problem is a crucial decision, and it has the advantage of working with the infrastructure in place instead of trying to replace it. Such a network could be easily deployed in today’s internet, and based on the evaluation of its merit could someday become the dominant protocol.
• By decoupling the sender from the receiver i3 is able to implement a variety of services. Using indirection is a key design point that enables flexible communication between hosts. This transition to rendezvous-based communication  is a marked improvement over the point to point model.
• As the way that we use the internet has evolved, security has become a primary concern because of the services that are delivered over the internet. The problem is that the protocols in use today were not designed with security in mind. Any new idea for internet architecture should make sure to address security concerns. The paper comments on issues that are particularly relevant such as eavesdropping and DoS attacks.  The ability to have private triggers, enforcing that only a host can insert triggers on its own behalf, and fair queuing are all important extensions.

Glaring Problem:
A major concern with i3 is that the end hosts are responsible for inserting triggers, which means that it would be hard to enforce order and structure in the resulting overlay network. I would have liked to see the paper address this more fully, and maybe elaborate on how a large scale network could evolve out of an ad hoc, approach. This is discussed in the context of preventing attacks, but not in terms of how the network should be structured.

Future Work:
The i3 overlay is presented to us as a general mechanism for implementing communication abstractions. It would be interesting to see what other abstractions could be implemented with i3 in its current form or with extensions.

Internet Indirection Infrastructure April 16, 2009

Single overlay capable of achieving multiple communication services over a P2P network
The paper comes up with a single infrastructure capable of supporting several services such as multicast, broadcast, anycast, mobility etc over the Internet architecture with was built to be P2P. It achieves this by introducing a level of indirection in the form of nodes that act as i3 servers. Senders direct outgoing messages to identifiers instead of a particular destination node address. Receiving nodes can then subscribe to these identifiers if they wish to the message. Hence, more than one receiver can subscribe to an identifier, thereby allowing for the above mentioned services to be achieved over a P2P network. This method suggested by them provides for a lot of flexibility in the terms of the types of services that can be provided, nodes that can add or drop themselves to a service, etc. Other than providing for these services, their structure achieves security (in some aspects, while giving rise to different set of security concerns that they consider in detail and provide methods to counteract) which couldn’t have been achieved in a P2P system.

Methods to add new nodes, handle failure of old ones and provide efficient routing
In addition to suggesting the basic infrastructure, the paper also talks of efficient methods implementation of the idea. The first question that comes to mind when the i3 structure is suggested is, the overhead it would add. The paper provides for a method of packet forwarding that seems to add minimal overhead. In the method suggested, the senders cache the address of the server that is responsible for routing packets to the identifier the sender wishes to send packets to. This reduces the time to find the server for subsequent sends. The receivers reduce the time to receive packets from the servers by choosing servers close to themselves. Similarly, the paper also suggests efficient methods to deal with node failures, node additions and packet forwarding.

Methods to handle security threats
The nature of how the i3 system works exposes it to several security threads. The paper makes a detailed analysis of all possible threats and suggests methods to counteract them.

PROBLEMS

The paper claims that it handles the triangle problem by getting the receiving nodes to choose a server close to themselves to store the trigger containing their id. However, this solution only works if the system has a large number of i3 servers. If there exist only a few servers for a large number of nodes, it is likely that two nodes, adjacent to one another, might have to communicate with a far away server node to be able to reach one another.

Several of the methods they suggest to handle the issue of security work by inhibiting free and flexible use of i3 by the servers. For eg, one of the methods limit the number of triggers a node can have. Also, the innate structure of i3 introduces far too many means of intrusion to be able to detect and counter every one of them.

In spite of several methods to reduce overhead, the structure still introduces them at various stages and steps. There is the overhead introduced by in the security methods suggested, enabling caching by the appropriate server sending out the, “it is me you want to send future messages to” message, etc.

FUTURE WORK

It seems like i3 would provide a workable and efficient platform for a network of rapidly moving nodes. it seems to have the mechanisms in place to provide support for such a system. Work could be done to explore possibilities in the area.

IP Switching-ATM Under IP April 9, 2009

“IP Switching-ATM Under IP” by Peter Newman, Greg Minshall and Thomas L. Lyon is a paper about running IP over ATM. The internet and private enterprise networks traffic have been growing exponentially. To deal with this the authors suggest running IP over ATM because the ATM switching technology offers higher aggregate bandwidth. This gives the simplicity, scalability, and robustness of IP with the speed, capacity and multiservice traffic capabilities of ATM.

The authors start off the paper describing the need for IP over ATM. They bring up the cost difference for a router with limited throughput compare to a switch with more throughput. After mentioning why it is necessary to use IP over ATM, the authors show why other methods that try IP over ATM are incorrect. This is mainly due to the fact that the approaches hide the underlying network topology from IP so it is just an obscured cloud to IP.

The authors approach starts off by replacing the ATM software with a protocol they created called general switch management protocol. This protocol allowed the IP switch to control the hardware switch in ATM. They used soft states to cache flow information and allowed each switch to locally decide which flow to use as there basis in their design. They determined flows using the IP/TCP/UDP headers classifying the flows into two types, port-pair and host-pair. One important part of the paper is the point-to-point network model rather than a logical shared medium. This works because point-to-point is more natural for ATM and have been proven to scale to very large networks by the Internet. Another important part of the paper is the multicasting using IP over ATM. When an incoming multicast flow comes in, it will branch out to multiple destinations. Each of these branches can be redirected by a downstream neighbor. If the flow happens to be labeled, we can use the hardware multicast capabilities of the ATM switch. The last important part of the paper is the QOS. The authors were able to support both policy-based and contract-based quality of service. They supported contract-based QOS with RSVP to simulate something similar to ATM traffic management.

The paper’s impact on the future of networking can be seen from that fact that they are planning for the future. The future trends show traffic growing at a rate that the technology cannot efficiently handle. What makes this paper interesting in this sense is the fact that they used previous technology to address the problem instead of creating something new. A problem with this paper is their solution cannot detect loops from previous switched flows that differ only in TTL.