Project topics and materials
Get Complete Project Material File(s) Now! »
Computer Networks
In 1962, L. Kleinrock introduced networking based on packet switching [134]. Before that, communication between two points (nodes) was only possible by establishing a persistent electri-cal circuit between them, through which data could be sent. That was the principle of the Public Switched Telephone Network (PSTN), where a set of terminals or endpoints (typically, but not only, telephones) were connected through a set of wires and telephone switches. These switches were responsible for establishing a persistent circuit between the calling terminal and the called terminal. Once the circuit was established, its use was exclusively reserved to the two connected endpoints. Such circuit (telephone call) was maintained until the end of the communication (e.g., voice con-versation), after which the connection was closed. Figure 1.1.a illustrates the main characteristics of PSTN calls: during the call between terminals A and C, no other terminal is able to establish communication with either A or C, as the circuit between A and C is persistent and exclusive. Packet switching is based on a different approach (see Figure 1.1.b). Rather than com-municating by establishing persistent circuits between endpoints, the use of data packets permits using the same channel (e.g., a wire) to provide support for simultaneous communications between many different pairs of endpoints. Data to be sent from a source to a (set of) destination(s) is en-capsulated in data units, called packets, each of which can be treated autonomously and separately. These packets may need to be forwarded by one or more intermediate nodes before reaching their final destination(s).
This approach enables more flexible communication between nodes within a network than the circuit-switching approach, as it enables any endpoint to maintain several communications con-currently. By not dedicating the channel to a particular pair of endpoints, it also allows a more effi-cient use of the channel. This is at the expense of lowering reliability of communication: packets in a packet-switching network may be lost or delivered out of order. Characteristics of circuit switching are appropriate for requirements and properties of voice transport (reliable communication, delivery of data in the same order in which it was sent, balanced amount of data in both directions); packet switching, in turn, has become the basis of computer networking, and in particular the Internet.
Outline
This chapter presents the main elements of computer networks and the Internet. Section 1.2 presents the basic terms and concepts of computer networking – network, interface, link, routing and routing protocol. While many terms are in common use in networking research, they are defined formally in this section in order to avoid ambiguity and clarify the precise meaning and the sense in which they are employed throughout this manuscript. Section 1.4 addresses the interconnection of existing networks (internetworks), presents the concept of internetworking and provides an architec-ture overview of the most prominent case of internetwork – the Internet. In particular, the section describes the IP addressing model and the Internet routing hierarchy. Finally, section 1.5 concludes the chapter.
Networking and Routing Concepts
This section presents and discusses the basic elements of computer networking. Section 1.2.1 defines the concepts of packet, computer network, interface and link. Section 1.2.2 presents the graph representation of a network and discusses its interest as analysis tool. Based on these definitions, section 1.3 elaborates on the conditions that need to be fulfilled in a computer network so as to ensure that information can be exchanged between computers.
Networks and Links
A computer network is defined as follows:
Definition 1.1 ( Packet computer network ). A computer network is a set of two or more computers that are connected in such a way that every pair of computers can exchange information. A packet computer network or packet-switching computer network is a computer network in which information is exchanged by means of packets, i.e., data units that contain sufficient information about their source and destination(s) to be routed and delivered separately through the network. Unless otherwise specified, all references to networks relate to packet computer networks.
Computers are connected to other computers in a network through links.
Definition 1.2 ( Link between computers ). There is a link between two computers A and B, denoted by A −→ B, if and only if A is able to transmit data to B and B is able to receive such data, without intervention of any other computer.
Definition 1.3 ( Symmetric link between computers ). A link between two computers A and B is said to be symmetric (or bidirectional ), and denoted by A ←→ B, if and only if there are links
18 Chapter 1: Computer Networks
A −→ B and B −→ A, i.e., data can be transmitted from A and received by B and vice versa, without intervention of any other computer.
A computer participates in a link by way of a network interface:
Definition 1.4 ( Network interface ). A network interface of a computer is a device that provides access from that computer to a link through an underlying physical communication channel.
In this sense, link definitions 1.2 and 1.3 can be rephrased as follows, in terms of interfaces:
Definition 1.5 ( Link between interfaces ). There is a link between two network interfaces a and b, denoted by a −→ b, if and only a is able to transmit data (bits) to b and b is able to receive such data, without the intervention of any other interface.
Definition 1.6 ( Symmetric link between interfaces ). A link between two network interfaces a and b is said to be symmetric (or bidirectional ), and denoted by a ←→ b, if and only if there are links a −→ b and b −→ a, i.e., data can be transmitted from a and received by b and vice versa, without requiring the intervention of any other interface.
The existence of a link between two computers implies the existence of (at least) one link between two network interfaces of these computers. Let A and B be two computers, and let I(A) and I(B) be the set of network interfaces of A and B, respectively; then:
A −→ B =⇒ ∃a ∈ I(A), b ∈ I(B) : a −→ b
Reciprocally, the existence of a link between two network interfaces implies the existence of one link between the computers to which the interfaces are attached. In this manuscript, the term link denotes a link between network interfaces, unless otherwise specified.
Unless stated otherwise, the term link in this manuscript denotes a symmetric link. Non-symmetric links are explicitly called asymmetric links.
Depending on the number of interfaces in a link, different types of links can be distinguished. Figure 1.2 illustrates three different types of links and networks: broadcast links, point-to-point links and wireless links. The first two are defined in definitions 1.7 and 1.8; wireless links are described in chapter 2.
Definition 1.7 ( Point-to-point link ). A link l between two network interfaces a and b is a point-to-point link if and only if data can be transmitted from a to b (and/or vice versa) by way of l and no other interfaces x and y (x = a, b; y = a, b) can exchange information through the same link l.
Definition 1.8 ( Broadcast link ). A link l is a broadcast link for a set of network interfaces {xi}i≤k if and only if data can be transmitted from xi to xj for any value of i, j ≤ k, and a packet transmitted by any interface xi is received by every other interface in the network xj , j = i.
• Defs. 1.5 and 1.8 imply that links between different interfaces (e.g., a −→ b and c −→ d in Figure 1.2.a) may correspond to the same broadcast link. For a criterion to identify equivalent links, see the link equivalence relation presented in Appendix A.
• Broadcast links are always symmetric: for any interfaces a and b attached to such a link, data can be transmitted either from a to b or from b to a.
Definitions of broadcast and point-to-point links illustrate particular cases of the concept of link : both allow communication from one network interface to another through a physical com-munication channel – in the case of the broadcast link, in particular, information can be exchanged between any pair of attached network interfaces. Examples of point-to-point links include PPP1 (see Figure 1.2.c), while the most prominent examples for broadcast networks include Ethernet and Token-Ring technologies (the architecture of a broadcast network is displayed in Figure 1.2.a).
Broadcast and point-to-point categories do not cover all possible cases of link. Commu-nication between wireless network interfaces, in particular, cannot be modeled in general by any of these two definitions: in the example of Figure 1.2.b, the wireless link between b and c is not a point-to-point link (as packets sent from b to c are also received by a) and neither is a broadcast link (in particular, a cannot receive packets sent by c). Properties and challenges of wireless links and networks are discussed in detail in chapter 2.
Graph and Hypergraph Representation
The topology of a computer network at a particular point of time can be represented as a graph G = (V, E), in which the set of vertices V corresponds to the set of attached computers and the set of edges V indicates the presence of links between computers. Such graph G is called network graph throughout this manuscript, and is assumed to be connected – otherwise, G denotes the network corresponding to a connected component of the graph instead. Given two vertices x and y of V , the edge xy is included in E if and only if there is a link between computers represented by x and y. Asymmetric links are represented by directed edges, while symmetric links correspond to undirected edges.
The graph representation of a network is useful for a number of purposes, and is used throughout this manuscript to analyze properties of networking and routing algorithms from a theoretical perspective. For instance, the path that a packet follows from a source computer, x, to a destination computer, y, can be represented as a path through the network graph, pxy .
Table of contents :
Introduction
Structure and Overview
I NETWORKING FUNDAMENTALS
1 Computer Networks
1.1 Outline
1.2 Networking and Routing Concepts
1.2.1 Networks and Links
1.2.2 Graph and Hypergraph Representation
1.3 Addresses, Direct and Indirect Communication
1.4 Connecting Networks
1.4.1 IP Addressing and IP Links
1.4.2 Network Reference Models
1.4.3 Routing in the Internet
1.5 Conclusion
2 Wireless Computer Networking
2.1 Outline
2.2 Wireless Communication
2.2.1 Frequency of Wireless Signals
2.2.2 Coverage and Interference in Wireless Interfaces
2.2.3 Wireless Links
2.2.4 Semibroadcast Properties of Wireless Communication
2.3 Wireless Networks under the IP Model
2.3.1 IEEE 802.11
2.4 Conclusion
3 Communication in Ad hoc Networks and Compound ASes
3.1 Outline
3.2 Ad hoc Networks and Compound ASes
3.2.1 Ad hoc Networks and Applications
3.2.2 Compound Autonomous Systems
3.3 Nodes, Links and Addresses in Ad hoc Networks
3.4 Single and Multi-Hop Communication
3.4.1 Neighbor Sensing
3.4.2 Routing in Ad hoc Networks and Compound ASes
3.5 Conclusion
II LINK-STATE ROUTING IN AD HOC NETWORKS
4 Elements of Link State Routing
4.1 Outline
4.2 The Link State Database
4.3 Topology Acquisition
4.3.1 Flooding
4.3.2 LSDB Synchronization
4.4 Issues in Ad hoc Networks and Compound ASes
4.4.1 General Bandwidth Constraints
4.4.2 Flooding over Wireless Interfaces
4.4.3 LSDB Synchronization in Compound ASes
4.5 Conclusion
5 Packet Jittering for Wireless Dissemination
5.1 Outline
5.1.1 Terminology
5.2 The Jitter Mechanism
5.2.1 Common Input and Common Configuration
5.2.2 Wireless Collisions and Jitter in Link-State Routing
5.2.3 Forwarding Flooding Packets with Jitter
5.3 Analytical Model
5.3.1 Traffic Model and Assumptions
5.3.2 Message and Packet Rates
5.3.3 Statistical Description of Traffic to be Forwarded
5.3.4 Time to Transmission for a Received Message
5.3.5 Discussion of Results and Model Limitations
5.4 Simulations
5.5 Conclusion
6 Overlays in Link State Routing
6.1 Outline
6.2 LS Routing in terms of Overlays
6.2.1 Topology Update Flooding
6.2.2 Point-to-point Synchronization
6.2.3 Topology Selection
6.3 Full Network Overlay
6.3.1 Full Network Topology Flooding
6.3.2 Full Network Synchronization
6.3.3 Overall Control Traffic
6.4 Conclusion
7 The Synchronized Link Overlay Triangular – SLOT
7.1 Outline
7.2 Definition, Related Overlays and Variations
7.2.1 Gabriel Graphs and Relative Neighborhood Graphs
7.2.2 The Synchronized Link Overlay and SLOT
7.2.3 SLOT-U and SLOT-D
7.3 Performance Analysis for 2-Dimensional Networks
7.3.1 Overlay Density
7.3.2 Link Stability
7.3.3 Validation
7.4 Performance Analysis for Other Dimensions
7.4.1 1-Dimensional Networks
7.4.2 3-Dimensional Networks
7.5 Selection of Links depending on Distance
7.6 Conclusion
8 Multi-Point Relays – MPR
8.1 Outline
8.2 Definitions and Heuristics
8.2.1 Heuristics
8.2.2 Implications
8.3 MPR as a Flooding Overlay
8.4 MPR as a Synchronized Overlay
8.4.1 Asymptotic Connection and Density
8.4.2 Link Change Rate and Persistency
8.5 MPR as a Topology Selection Rule
8.5.1 Path MPR
8.5.2 Enhanced Path MPR
8.6 Conclusion
9 The Smart Peering Technique – SP
9.1 Outline
9.2 Definition and Specification
9.3 Asymptotic Properties
9.4 Reaction to Mobility
9.5 Conclusion
III APPLICATION TO OSPF
10 LS Routing Protocols within an AS
10.1 Outline
10.2 Open Shortest Path First – OSPF
10.2.1 Architecture and Terminology
10.2.2 Areas, Interfaces and Neighbors
10.2.3 Packet and Message Types
10.2.4 Single-Area OSPF for Non-Broadcast Networks
10.3 Intermediate System to Intermediate System – IS-IS
10.3.1 Architecture and Network Partitioning
10.3.2 Interface Types
10.4 Conclusion
11 OSPF MANET Extensions
11.1 Outline
11.2 IETF Standard Extensions
11.2.1 Multipoint Relays – MPR-OSPF
11.2.2 Overlapping Relays & Smart Peering – OR/SP
11.2.3 MANET Designated Routers – OSPF-MDR
11.3 Improved MPR-based Extensions
11.3.1 Persistency Variations of MPR-OSPF
11.3.2 SLOT over MPR-OSPF – SLOT-OSPF
11.3.3 Multipoint Relays + Smart Peering – MPR+SP
11.4 Conclusion
12 Performance Evaluation of OSPF via MANET Simulations
12.1 Outline
12.2 Synchronization & Optimal Routes in OSPF and MANET Extensions
12.2.1 User Data over Shortest Paths
12.2.2 User Data & Control Traffic over Synchronized Links
12.3 Neighbor Sensing Optimization
12.3.1 Proactive and Reactive Synchronism Recovery
12.3.2 Overhead Impact
12.4 Main Link-State Operations
12.4.1 Flooding
12.4.2 Topology Selection
12.4.3 LSDB Synchronization
12.4.4 Control & Total Traffic
12.5 Persistency Impact on MPR-OSPF
12.5.1 Persistent Adjacencies and Data Routing Quality
12.5.2 Control Traffic Structure
12.6 Conclusion
13 Experiments with OSPF on a Compound Internetwork Testbed
13.1 Outline
13.2 Testbed Description
13.2.1 Interfaces Configuration and Network Topology
13.2.2 OSPF Routing Configuration
13.3 Experiments and Results
13.3.1 Wireless Multi-hop Communication
13.3.2 OSPF Control Traffic Pattern
13.4 Conclusion
Conclusions
Summary of Contributions
Perspectives and Future Work
Final Remarks
Bibliography
