Computer Networks Laboratory: Electrical Engineering Department, Technion

Setting New Barriers in Cellular/Wireless Communications
Yoram Rimony
Director Engineering, Qualcomm Israel Ltd (yrimoni@qualcomm.com)

In the first part, the lecture shall cover the migration path from legacy cellular voice centric system to new IP based technologies and shall uses QUALCOMM Israel latest development in this area as an example. The second part shall provide a more larger view of new development in the cellular/wireless industry aimed to drive the technology to be packet data centric in most cases and provide the users with new multi-media options.

Sizing Router Buffers
Dr. Isaac Keslassy
Dept. of Electrical Engineering, Technion

All Internet routers contain buffers to hold packets during congestion.
Today, the size of the buffers is determined by the dynamics of TCP. A widely used rule-of-thumb states that each link needs a buffer of size B = RTT X C, where RTT is the average round-trip time of a flow passing across the link, and C is the data rate of the link. For example, a 10Gb/s router linecard needs up to 250ms X 10Gb/s = 2.5Gb of buffers.
Such large buffers are challenging for router manufacturers, who must use large, slow, off-chip DRAMs. And queueing delays can be long, have high variance, and may destabilize the congestion control algorithms.
In this talk, I will take the (controversial) stand that this rule-of-thumb B = RTT X C is now outdated and incorrect for backbone routers because of multiplexing effects. I will show that a link with n flows requires no more than B =(RTT X C) / sqrt{n}. The consequences on router design are enormous: A 10Gb/s link carrying 50,000 flows requires only 10Mb of buffering, or 0.4% of the widely used value. This new value can easily be implemented using fast, on-chip SRAM.

A View of New Pervasive Paradigms
Prof. Imrich Chlamtac
President, CreateNet Research Consortium
Bruno Kessler Honorary Professor, University of Trento
Distinguished Chair Professor of Telecommunications
The University of Texas at Dallas

As the trend toward ubiquitous and pervasive computing continues to gain
momentum, new networking paradigms need to be developed to keep pace
with the needs of this emerging environment. In the near future we can
expect the number of nodes to grow by multiple orders of magnitude as
tags, sensors, body networks etc., get fully integrated into the
communication superstructure. Not only will the amount of information in
these all-embracing pervasive environments be enormous and to a large
degree localized, but also the relaying needs for maintaining an end to
end reliable `always on` networks, as we know today, will be, for the
vast majority of the pervasive users beyond their resource capabilities,
and in addition redundant, considering the needs of the personalized
services dominating these networks. The ambience within which these
nodes will act will be intelligent, mobile, self-cognitive and not
limited to machine to machine communication. In these networks the end
to end concept of always on communication that formed the basis of the
Internet for the last three decades will become passe.
This talk will discuss the concept of Nomadic Pervasive networks
exploring a new communications paradigm in which, compared to classical
networking architectures, nomadic users locally self-organize to form a
network when the opportunity or need arise, and adjust and evolve over
time with the application at hand. Given this "evolutionary nature" of
the emerging pervasive systems, we show how network behaviour and
control can follow organic world rules based on evolution and genetics.
This model can be specifically applied to mobile sensor networks where
the resulting reduced networking functionality, allows for minimal
sensor node requirements and significant costs saving in the overall
sensor network design, thus removing the existing barrier to sensor
networks market acceptance.

Using multi-rail networks in high-performance clusters

Dr. Eitan Frachtenberg
Los Alamos National Laboratory

Clusters of independent nodes communicating with a high-performance interconnect are increasingly growing in number and size. To obtain better bandwidth and fault tolerance from the network, some clusters use multiple independent networks (rails), using redundant NICs, switches, and I/O buses.
The question then arises of how to allocate rails to messages in a way that increases performance and reduces contention. Each rail allocation scheme must meet the following requirements:
(1) Every node can transmit to every other node without passing through intermediate nodes,
(2) Bidirectional traffic on the I/O buses must be avoided, and
(3) Rails are independent: messages cannot pass from one rail to another.

We discuss five rail allocation schemes: static, round-robin, local dynamic, reserved dynamic, and hybrid. The first allocates rails statically, so that a node can only transmit or receive on a given rail. While easy to implement, meeting the three requirements imposes a substantial lower bound on the required number of rails. The other four methods allocate rails dynamically, using round-robin allocation, local information, coordinated protocols, or a hybrid of methods, respectively. A comprehensive evaluation of each scheme in the context of ASCI Q was performed and we compared the relative merits of each scheme in terms of performance, message striping capabilities, scalability, and saturation loads.
We found that the dynamic rail allocation schemes generally outperform static schemes in terms of bandwidth and latency using fewer rails. Within dynamic schemes, protocol-free methods such as local dynamic perform better for short messages, while reservation schemes are better-suited for long messages. A hybrid method can actually combine the advantages of both, and increase the network's effective bandwidth by 8-49%, compared to other schemes.

Joint work with Fabrizio Petrini and Salvador Coll.

QoS Provision and Routing with Deterministic and Stochastic Guarantees

Erez Biton

Electrical Engineering Department, Technion.

End-to-end Quality-of-Service (QoS) provision and routing are central and critical issues in the design of integrated multimedia networks. Indeed, end-to-end support for QoS has been widely investigated. In particular, scheduling disciplines for guaranteed performance service as well as worst-case end-to-end performance bounds have been established and explored in a large number of studies, under both deterministic and stochastic settings. Recently, the corresponding routing problems have been addressed as well. However, a comprehensive study, which considers both problems, i.e., the establishment of end-to-end performance bounds and the corresponding routing problems, has not been reported. Since these two problems are closely related, moreover the former is a prerequisite for the latter, in this research they are investigated as a whole. In other words, this work presents a methodology for providing QoS guarantees by considering the coupling between the scheduling mechanism and the routing schemes. More specifically, we consider QoS provision and routing schemes for connections with end-to-end delay requirements in networks that employ rate-based schedulers.

In the first part of the presentation, we focus on the GPS scheduling discipline. Here, we study three settings: (i) burstiness-constrained (BC) traffic with deterministic QoS requirements, (ii) exponentially bounded burstiness (EBB) traffic with stochastic QoS requirements, and (iii) (general) stochastic bounded burstiness (SBB) traffic. Then, we turn our attention to the rate-controlled EDF scheduling discipline. Here, we consider both BC as well as EBB traffic. For each, we obtain end-to-end delay bounds for packetized traffic and links with non-negligible propagation delays, and, consequently, we formulate appropriate routing schemes that identify feasible paths under several network optimization criteria.

Finally, we consider the provision of QoS in fault tolerant networks. Here, the required QoS is given in terms of call termination probability upon resource failures. We consider the optimal admission control policies for two network models, namely, optical networks with shared protection and wireless networks.

Layer 7 Intelligent Networking Devices

Michael Ben-Nun

CTO of P-cube, which was acquired by Cisco

Traditional networking devices only deal with layers 1 to 3: Physical, Data link and Networking layers. Networking devices today process and control traffic based on to layer 7 attributes. This evolution will migrate the internet in the near future from a global network that provides connectivity, to an active and intelligent network that enable advanced services as well as new business models.

In this talk, we will discuss the motivation and benefits for having a layer 7 networking devices as well as the challenges of designing them. We will provide a quick look at the inherent architecture requirements from such a device and scan some of the favorite layer 7 protocols, such as Peer to Peer, Streaming, Voice over IP (VoIP), etc.

In addition to the advanced services we will show that securing the network from attacks and worms also call for an intelligent device, which is capable of analyzing the network at layer7, scan the traffic using signatures, and heuristics that can provide a "cleaner pipe".

The intelligent network is the next wave which will continue in the next few decades, therefore only the tip of the iceberg can be uncovered today. The rest of the iceberg is subject to research and imagination, which hopefully will be triggered by this talk.

The application of game theoretic models and tools in the area of networking
has been gaining increasing attention in recent years. From what was a
rather "esoteric" area of research not many years ago, it has grown to be
well within the mainstream of the networking research agenda.

In this talk we shall overview the major stages in the evolution of
this area. First, we shall move back 4-5 decades and examine some of the
early (game theoretic) advances in related fields such as queuing systems and
transportation networks. Then, we shall move on to about 2 decades ago, and
examine the early steps of game theory in communication networks. We will
consider the early motivation, contrast it with current motivation, and
overview some of the (early) fundamental results in flow-control and routing
games. Moving on to more recent studies, we shall observe the main issues at
stake, namely characterization of the network properties and performance in
a noncooperative environment, and an attempt to improve the inherent
inefficiency that stems from unregulated behavior, via proper design and
management (in particular, pricing) tools. We shall conclude by outlining
several current challenges and opportunities for future work.

MaGMA is a Mobility and Group Management Architecture enabling
real-time collaborative group applications such as push-to-talk (PTT) for mobile users.
MaGMA provides, for the first time, a comprehensive and scalable
solution for group management, seamless mobility, and quality-of-service (QoS).
MaGMA is a distributed IP-based architecture consisting of an overlay
server network deployed as part of the service infrastructure. The
architecture is very flexible, and can co-exist with current as well as
emerging wireless network technologies. We see such services as
essential components in beyond-3G (B3G) networks. MaGMA incorporates a
number of group management protocols,which are appropriate for different group and network scenarios.
We have implemented the MaGMA protocols in ns2 and evaluated them
through simulation and analysis. We also have built a proof-of-concept
prototype implementation.

Wireless ad-hoc networks are formed when an ad-hoc collection of devices equipped with wireless communication capabilities happen to be in proximity to each other. Clearly, each pair of such devices whose distance is less than their transmission range can communicate directly with each other. Moreover, if some devices occasionally volunteer to act as forwarders, it is possible to form a multiple hop ad-hoc network. An important distinguishing element of these networks from "standard"
networks is that they do not rely on any pre-existing infrastructure or management authority. Moreover, due to mobility, the physical structure of the network is constantly evolving.

Semi-reliable multicast is a basic service for many collaborative applications as it provides nearly reliable dissemination of the same information to many recipients. It ensures that most messages will be received by most of their intended recipients. Yet, implementing semi-reliable multicast in an efficient manner, and in particular over a wireless ad-hoc network, is far from trivial.
It involves ensuring that a message is forwarded to all nodes as well as overcoming possible message losses.

Unlike infrastructure based networks in which routers are usually considered to be trusted entities, in ad-hoc networks routing is performed by the devices themselves. Thus, there is a high risk that some of the nodes of an ad-hoc network will act in Byzantine manner, or in other words, would not respect the networking protocols. This can be a result of maliciousness, or simply selfishness (trying to save their own battery's power).
Thus, the possibility of having Byzantine nodes in the system motivates the development of Byzantine tolerant multicast protocols for ad-hoc networks.

In this talk I will present an overlay based Byzantine tolerant multicast protocol for wireless ad-hoc networks. The use of an overlay results in a significant reduction in the number of messages. The protocol overcomes Byzantine failures by combining gossiping of message signatures and failure detectors. These ensure that messages dropped by Byzantine nodes will be detected and retransmitted and that the overlay will eventually consist of enough correct processes to enable message dissemination. An appealing property of the protocol is that it only requires the existence of one correct node in each one-hop neighborhood. The hypothesis behind this protocol is validated using extensive simulations.

* Joint work with Vadim Drabkin and Marc Segal

The evolution of the Broadband Wireless Access and the revolution of the WiMAX as the 4G technology

Mr. Zvika Harnik

Executive Vice President, Research and Development, Alvarion

ClubNet Winter 2005