Computer Network Technology

________________________________________________________________________________________________

Communications activities are treated in several chapters of this Research Report. In this section, we concentrate on general communications matters - as distinct from Section 5 which concentrates on network management issues. The subject area, and the Department, are moving beyond Ethernet LAN speeds and 2 Mbps WAN networks. Moreover, some of the applications we are pursuing, particularly the multimedia ones, require higher speeds to operate well. We are accommodating our normal higher speed service needs by our attachment to the College FDDI network, and by moving over to an Ethernet Hub solution locally; these aspects are described in Appendix 1. The Wide Area connectivity at higher speeds is provided by the College Information Systems Division (ISD) in its connection to SuperJanet. However, actually making the wide-area infrastructure work is requiring collaboration between ISD and UCL-CS; extending to our department requires considerable activity by some of the research projects. We are equipping the department with at least a rudimentary ATM LAN facilities, several ATM switches, and direct connections to the ISD switches connected into SuperJanet. Several of our communications projects, particularly in the context of the European RACE program and our collaborations with BT/UKERNA under SuperJanet auspices, will shortly start using the concatenated ATM LAN/WAN communications systems in earnest. For some purposes we care about the technology used; it is relevant, for example, that it is ATM. For others it is only important that there be higher speed connections; for these the WAN aspects are sometimes IP/ATM and sometimes IP/SMDS. In Section 4.1 we describe both the infrastructure being built up inside the department, and the activities which plan to exploit this LAN/WAN infrastructure over the next year.

We are very concerned with the integration of LAN and WAN facilities; in Section 4.2 we describe our activities both in flow control for local ATM access, and in the provision of services over the concatenation of narrow-band ISDN and LANs. At a different level, we are deeply involved in the effort to provide a fully functional next generation of concatenated networks; our activities here are treated in Section 4.3. The work includes mechanisms for policy based routing and traffic control, multicast routing, and light-weight protocols to allow the techniques to work at higher speeds. Much of the work is, by its nature, in close collaboration with others both in Europe and overseas (particularly the US, but also Australia).

The Departmental ATM
Infrastructure

Broadband Networking Infrastructure

Jon Crowcroft

Over the past year, we have been building up an ATM infrastructure so that we can conduct real experiments. Currently, we have one lab with most machines equipped with ATM adaptors, capable of providing raw ATM Cell level access, or IP over AAL4 or AAL5. The machines are all on a Fore ASX100 switch, which is connected to the College Information Systems Division Fore ASX200. That in turn is connected to the College's Netcomm (General Datacomm) DV2 ATM switch, which is part of the 12 site SuperJANET ATM pilot. That, in its turn, is connected via an Alcatel switch to the BT National Pilot, the BT Labs ATM infrastructure, and to the pan-European ATM PNO pilot . This will feature as part of the RACE PREPARE demonstrator network, which is centered around KTAS in Copenhagen, and includes the Danish BATMAN national pilot, as well as Berkom. Managing this network, the services on it, and interconnecting different management systems are part of the work on the RACE projects, ICM and DRAGON.

In December 1994, we connected a second switch to the raw 2*34Mbps transmission capacity available on the SuperJANET network, and onwards to Imperial College and to the Computer Laboratory in Cambridge. We shall shortly be receiving another two switches, one under a research donation from Hewlett Packard, and the other from NKT as part of the PREPARE project.

A dedicated link between the Department of Computer Science and the Information Systems Division at UCL, who operate the College central computing and communications facilities, also provides high bandwidth into the SuperJANET IP over an SMDS access router. This may prove to be our most stable path for application projects such as MICE, RELATE and DRAGON to provide multimedia conferencing towards those sites in other European countries whose access to the PNO pilot (or even SuperJANET) is restricted to an SMDS service.

Figure 4.1

The PREPARE ATM Testbed.

Piloting ATM

Jon Crowcroft, Alina da Cruz, David Lewis, Anne Hutton, Peter Kirstein, Tore Riksaasen and Athanassios Tiropanis

As outlined above, an infrastructure is now being assembled that leaves UCL well placed in the piloting of service over ATM both in the UK and across Europe. As well as the planned activities over ATM in the BT University Research Initiative and the piloting of the use of ATM for M-BONE traffic, UCL is one of the early users of the European PNO ATM Pilot through its work in the PREPARE, MICE and DRAGON projects. This work is in the form of a testbed network (shown in the figure below) consisting of at least one Fore ATM LAN switch and one NKT ATM cross connect (XC) at UCL, CS, GMD-FOKUS in Berlin and KTAS in Copenhagen. These three sites are interconnected by International PNO Pilot ATM links and the national ATM pilots in the U.K. and Germany. The Danish ATM Pilot (BATMAN) has already played an integral part in existing broadband network piloting work in PREPARE where it has been interworking with DQDB MAN equipment and ATM multiplexors for the attachment of multimedia application workstations. The completed testbed will support the operation of BERKOM II Multimedia Mail and MICE Multimedia Conferencing applications by providing access between multiple workstations at each site to a multimedia mail global store server at GMD-FOKUS and a conferencing multiplexing server at UCL.

Trials consisting of the three Fore switches connected directly over the international links, and supporting the multimedia applications operating over IP, are being conducted in advance of an initial public demonstration in 1995.

The DRAGON configuration is identical for the UCL site. Now, however, SEL Alcatel in Stuttgart, Germany and Telesystems, Paris, France will have only SMDS access to the European pilot. The MICE configuration is identical for the UCL site. Now, however, ATM access will be provided for SICS and KTH (Stockholm, Sweden), Oslo University and NTR (Oslo, Sweden), RUS and GMD (Gemany) and INRA (France). Some of them will use ATM access, some SMDS.

Multi-Service Traffic

Generic Flow Control for a Local
Access ATM Network

John Pearce (supervised by Steve Wilbur )

An essential element of B-ISDN is the Customer Network (CN) - sometimes called the Customer Premises Network (CPN) or Subscriber Premises Network (SPN). These can exist in a variety of formats from residential, through small to large business, and factory CNs. A CN covers the area over which users have access to the public Asynchronous Transfer Mode (ATM) network.

The ATM cell header at the User-Network Interface (UNI) is slightly different from that at the Network-Network Interface (NNI) - part of the Virtual Path Identifier (VPI) field is replaced by a 4-bit Generic Flow Control (GFC) field. Unfortunately this means that, unlike Ethernet, ATM has become a non-concatenative protocol and a device must be compatible with the available interface.

A GFC protocol must support both multi-point and point-to-point configurations, and be capable of:

  1. Ensuring that all terminals can access their guaranteed capacities - this is necessary for all Constant Bit Rate (CBR) and Variable Bit Rate (VBR) terminals with an element of guaranteed capacity.
  2. Distributing remaining spare capacity fairly amongst all VBR terminals.
  3. Supporting different delay and delay variation (jitter) requirements.
  4. Direct terminal-to-terminal communication.
  5. Insensitive to traffic mix as well as system parameters.
  6. Sufficiently robust to loss of GFC information.

This is a challenging requirement with only a 4-bit field to implement a GFC protocol. ITU-T Study Group 13 is currently deadlocked on the subject of multi-point GFC with competing proposals from BT/NTT and Ascom/ATRI. As a possible compromise a distributed queuing protocol (based on DQDB) with cyclic regeneration of virtual tokens (based on ORWELL) has been designed and simulated for a dual counter-rotating ring local access ATM network. The new TRIAL/RESET mechanism is less sensitive to the size of the network and offers more acceptable variation in access delay.

However, effectively and efficiently supporting the demands of a multi-service multi-QoS network is beyond the capabilities of a basic access protocol. Further research is in progress to consider the use of neural networks for the purpose of traffic control, congestion control, and more generally resource management in local access ATM networks.

Services into Packet-Switched
Networks

Stuart Clayman and Graham Knight

For some two years the department has operated a gateway between narrow-band ISDN and the departmental LANs. This gateway has been built around a Primary Rate ISDN interface board built in the department - the UCL Primary Rate Interface (UPI). Until recently this gateway acted exclusively as an IP router and supported a group of teleworkers who used PC or Unix-based systems, complete with Basic Rate ISDN interfaces and IP software, from their homes. Traffic through this gateway has increased steadily - stimulated in part by availability of better Internet applications such as the Mosaic interface to the World Wide Web. This work can be viewed as an extension of the data-communications world (embodied by the Internet) into the telecommunications world of ISDN.

Traditionally the telecommunications world has been the domain of isochronous applications such as voice and, more recently, video. The past couple of years has seen great advances in the provision of integrated services, including isochronous services, over the Internet. Applications such as VAT audio conferencing tool and IVS video-conferencing are now used extensively. It seemed natural, therefore to extend the capabilities of the UPI so it could support isochronous traffic. During the last year the software in the UPI has been modified to cope with the task of packetising and de-packetising 64Kbps isochronous traffic. A simple signalling protocol has been implemented for use between LAN stations and the UPI. This makes possible several interesting activities:

Many of the components which are needed are now complete; there are converters between the various voice and video encodings, software to recognise tone-dialling signals, modules to interface VAT conferences to telephone calls, etc. This work has benefited greatly from the efforts of a group of graduate students; Mike Brereton, Lionel Chaine, Ronan Flood, Dimitris Glitsos, Dimitris Kogias and Gary Telloke. The intention now is to put all these components together so that an experimental service can be offered.

Next Generation
Internetworking

Implementing Real Time Packet
Forwarding Policies using Streams

Atanu Ghosh, Jon Crowcroft and Ian Wakeman

The ARPA funded work has concentrated this year on getting the underlying network support for link sharing and performance guarantees for multimedia conferencing working. There have been two aspects of this: one is the CBQ work described here; the second is the CCCP work done in collaboration with MICE. A related piece of work has resulted in results for multimetric routing, and is described in Section 4.3.4.

Moves are now afoot to extend the Internet to support Integrated Services, based on the work of the INT-SERV working group of the IETF. It is envisiged that audio, video and other real-time services will be sent over the Internet, as well as supporting a more commercialised model of service, where the users and providers exchange money for a guarantee of a basic level of service. Since the service is dependent upon the mix of packets on the links and in the switches, the basic building block of the new Internet will be the forwarding scheduler on the output links. This must provide both a method for sharing bandwidth amongst the agencies who pay for the link, and provide appropriate levels of Quality of Service for flows with real-time requirements.

One vision of how to design this building block has been offered by Sally Floyd and Van Jacobson. They start from the premise of link sharing, where links are leased by multiple agencies who then require a guarantee of a share of the bandwidth when they need it. However if the bandwidth is not then used, other users can send packets. This can only be satisfied in any sensible manner in the scheduling of packets to be forwarded. Each of the agencies is guaranteed a minimum amount of the bandwidth, with the proviso that any instantaneously unused bandwidth is shared amongst the agencies in some previously agreed upon manner. This allocation of bandwidth can be naturally extended to provide the allocation mechanisms for real-time traffic, who require a share of the bandwidth and low delay forwarding.

The classifier interprets the header information of an incoming packet to determine the class of service that the packet should receive from the scheduler. It returns a pointer to the class structure that holds the queues and associated information. The packet is placed on the appropriate queue if the queue is not full. The output driver works asynchronously, determining from which of the non-empty queues to schedule a packet next output driver, according to the current utilisation of that queue and its priority.

The classification of a packet is very similar to the problem of determining the route matching a destination address in a packet, except that the patterns upon which the packet may match a class can be extended. For instance packets may be from one of multiple agencies, requiring the examination of destination and source addresses, classified on transport or other protocols such as TCP, UDP or ICMP, or applications such as ftp or telnet, requiring the examination of the port numbers. For video streams we may look even further within the packet to determine the level and loss tolerance of a packet within a hierarchically encoded video stream.

It is a point of some controversy as to how widely the above mechanisms need to be fielded within the Internet. It could be argued that they need only be used where the links are heavily utilised, and links which have low utilisation can supply the necessary Quality of Service for all types of stream with normal FIFO packet scheduling, since queues on the links are very small or non-existent. The current version of the CBQ filter is fielded on the UK-US FAT pipe across the Atlantic.

Multicast Routing Research

Tony Ballardie, Jon Crowcroft and James Kadirire

We have made great progress with multicast routing research this year. The Core Based Tree multicast work is being proposed in the ATM forum for multicast routing support for IP over ATM. Tony Ballardie has implemented CBT, and, having analysed security threats to multicast protocols, has designed an integral secure key distribution protocol that will be of great benefit not only to securing the network, but also for support for secure multimedia conferencing.

James Kadirire has designed a new multicast scheme for ATM VC multicast, which reduces the load on ATM switch copy fabrics.

Dynamic Multicast Routing In
Asynchronous Transfer Mode (ATM)
Networks

James Kadirire (supervised by Graham Knight).

There is an emerging demand for broadband services with more than 150 Mbps which require high speed switching and processing as well as high speed transmission. This can be realised by constructing a Broadband ISDN network using ATM technology. In large scale ATM networks the ability to multicast information will be necessary for many new and existing services.

Multicast can be defined as the ability to logically connect a subset of the hosts in a network. A packet switched network is said to provide a multicast service if it can deliver a packet to a set of destinations or a multicast group rather than just a single destination. With multicast routing, one is interested in the shortest (minimum cost spanning) subtree of the network containing a given set of hosts (the multicast group). One is not only interested in finding this minimum spanning tree, but also in minimising the cost of the routing calculations i.e. minimising the time complexity of the routing algorithm. This is essentially a Steiner Tree problem (STP) in graphs and is known to be NP-complete.

We have investigated some of the current dynamic multicast routing algorithms proposed in the literature. Our research has revealed the shortcomings of these algorithms and hence justified the need for more research into dynamic multicast routing algorithms.

The importance of geographic spread (GS) has been identified and it has been shown via simulations that spreading out the multicast connections 'geographically' in the network lowers the cost of the resulting multicast tree as well as the mean number of packet copies per node. GS is defined as follows: Given a graph G = (V,E), where V is the set of vertices and E is the set of edges, and a subset U of V, GS of the set U, in the static case when tree T' spans U, is defined as the inverse sum of the minimum distance from a vertex v to a vertex in T', over all vertices v in V. A new dynamic point-to-multipoint routing algorithm for ATM networks, named the Geographic Spread Dynamic Multicast (GSDM) routing algorithm, has been proposed and implemented. Multiple simulations have been performed to test the performance of the GSDM routing algorithm against the implementation of a well known Steiner tree heuristic commonly referred to as the KMB algorithm in the literature. The source rooted shortest path algorithm and the Greedy algorithm have also been implemented and the performance of the GSDM routing algorithm has been compared against these algorithms using randomly generated graphs to simulate the computer networks.

Routing Algorithms for Supporting Resource reservation

Jon Crowcroft and Zheng Wang

Multimedia applications, such as digital audio and video have much more stringent QoS requirements than traditional data applications. For a network to deliver QoS guarantees, it must make appropriate resource reservation and exercise necessary resource control. In the past several years, there has been much discussion and research in the area of resource management. Most of the work, however, focused on the problem of resource setup and resource enforcement at routers along an established path. Routing for supporting resource reservation is still an open research problem that has not been fully explored.

Routing should be an integrated part of any resource reservation system. When a host initiates a request for reserving network resources to another host or a router, the routing protocol has to first choose a path before the negotiation between the hosts and routers can take place. Therefore, the success or failure of a reservation request, to some large extent, depends on whether the routing protocol can choose the right path.

The process of resource reservation can be viewed as a two-step resource search. To find a path in a network that satisfies a set of requirements, the routing protocol first makes a high-level decision as to which path is more likely to have the necessary resources. The resource setup protocol then starts hop-by-hop low-level negotiation with each router on the path to sort out the fine details. To some extent, the decision making in routing is inherently more difficult due to its distributed nature.

Resource reservation has raised many new issues for routing. We believe that, in order to support resource reservation, major modifications are required in current routing protocols. In traditional data networks, the primary concern of routing has been the network connectivity. To support resource reservation, routing must however move towards a more resource-oriented system.

The key problem in supporting resource reservation is the complexity of such routing algorithms. Current routing protocols are already reaching the limit of feasible complexity. Adding the resource reservation support will inevitably further increase their burden. Our task is therefore to tackle the complexity problem by making sensible tradeoffs between optimality and complexity.

In this research, we propose two new routing algorithms for supporting resource reservation. In our algorithms, a path in a network is represented by its bottleneck bandwidth (width) and propagation delay (length). The algorithms find the shortest-widest paths from a given sources to all other nodes, using delay aided bandwidth search. The algorithms are scalable and loop-free in distributed hop-by-hop routing.

The Skynet Architecture

Jon Crowcroft, Mark Handley and Ian Wakeman

The SkyNet architecture, also known as lightweight sessions, has evolved from work at LBL, ISI, MIT and UCL. It is made up of these components:

There are a number of key design principles behind SkyNet Architecture architecture, but two foremost are:

  1. Application Layer Framing. (ALF). Only the application can sensibly decide the unit of packetisation and synchronisation.
  2. Integrated Layer Processing (ILP). Each layer should be implemented as far as possible as inline code.

A design rule of applications that run on the mbone is that all messages should be multicast. The problem with any other approach is simple implosion . If I ask a question of a large group, I may get many answers. If the group simply announce important facts periodically (and with a frequency in inverse proportion to the number of announcements, with a uniformly randomised phase difference of 1/nth of the period), then the system scales well. In particular, such session messages carry membership, media and reception quality information.

The potential demand for realtime multimedia is enormous. It is exceeded by the bandwidth in the fiber in the ground, but it far exceeds our financial ability to pay the current tarrifs.

As demand grows, we will see Delays increasing for traffic. Eventually, either the delay will exceed the acceptable bound for realtime users, or the demand will exceed available bandwidth, and loss will set in. At that point, some users may simply give up, and we will find a stable operating point for the supportable number of users.

Playout and Loss Adaption mechanisms can ameliorate problems. However, there are differences between users, and the current Internet does not act on these. As mentioned above, future enhancements to the Internet model will fix this problem, but do not need to be used by more than the people who need priority to work. Thus a peaceful co-existence of data, low priority multimedia, and high priority reservation traffic can emerge.

High Performance Protocol
Architectures

Jon Crowcroft and Atanu Ghosh

HIPPARCH is an ESPRIT Basic project investigating High Performance Protocol Architectures using Integrated Layer Processing (ILP) and Application Layer Framing (ALF) principles.

In 1994 UCL led the technical work, and at the end of the year a very successful workshop was organised for European and US researchers to present the state of the art in this area. In addition, UCL has been implementing a variety of applications in order to gain experience in applying the ideas from ALF and ILP. There are three things we have or are in the process of implementing:

  1. Vid - an integrated layer video decoder.
  2. Nt - A multicast based shared text editor .
  3. Slogin - a UDP based secure remote login program

We have also implemented the MICE Conference Control Channel Protocol (CCCP) and used it to build a Floor Control application.
(See ftp://cs.ucl.ac.uk/darpa/cccp.ps for details, and http://www.cs.ucl.ac.uk/people/jon/skynet/skynet.html for a general view )