Project topics and materials
Get Complete Project Material File(s) Now! »
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 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 .
Definition 1.9 ( Network path ). A network path between two vertices x, y ∈ V in a network graph G = (V, E) is a collection of edges of E, pxy = {xm1, m1m2, …, mk−1y} such that every pair of contiguous edges have one vertex of V in common. Given pxy , |pxy | = k denotes the length of the path, that is, the number of hops of the path.
However, the graph abstraction has some significant limitations that need to be taken into account. The most relevant is that different edges in a network graph do not necessarily indicate different links in the network: the same link may be represented by several (at least one) edges. Figure 1.3 illustrates some implications of this fact: networks with different architectures may present equivalent graphs.
For networks in which the number of interfaces (computers) participating in a link can be higher than two, such as broadcast or wireless networks, links do not necessarily correspond to edges and therefore, the graph representation cannot be used for analyzing aspects such as collisions or available bandwidth in a shared medium. The properties of wireless and mobile communication, in particular, impose additional constraints to the validity of network graphs, that are discussed in chapters 2 and 3.
For a more accurate representation in terms of collisions and link reachability, the notion of hypergraph may be useful, in particular for wireless ad hoc networks [23]. A network hypergraph ˜ ˜ is a pair H = (X, E) where X denotes the set of vertices and E denotes the set of hyperedges.
Vertices from X correspond, as for network graphs, to computers attached to the network; an ˜ hyperedge ex ∈ E, where x ∈ X, contains all the vertices corresponding to computers that receive a transmission from computer x, x itself included – in this sense, it generalizes the notion of edge, which is a particular case of hyperedge that only contains two vertices. Formally, an hyperedge ex is a subset of the hypergraph vertices (ex ⊆ X). Given that the number of vertices included that an hyperedge may contain is not restricted to two, hypergraphs are able to capture more accurately than graphs the connectivity and collision issues in networks where links may involve more than two interfaces.
Addresses, Direct and Indirect Communication
Communication between computers connected through links and networks may require that the interfaces involved in communication can be identified without ambiguity. These identifiers are called addresses.
For links that connect two and only two interfaces (point-to-point links), sender and receiver of a particular packet can be identified by the receiving interface even in the absence of addresses: there is no other possible receiver than itself, and there is no other possible sender than the other interface in the link. For links involving more than two interfaces, however, an interface identity is required. This identity, sometimes called physical address, has to be unique within the link in order to enable unambiguous communication with the rest of interfaces in the link.
The transmission of packets from one interface to another in a network requires that:
(i) interfaces have a unique address in the network (network layer address), so that source and destination(s) of packets can be unambiguously identified by including such addresses in the packets2,
(ii) interfaces agree in the formats and procedures to communicate (network technology).
These two conditions are sufficient for enabling communication between network interfaces in the same link: packets are then delivered in a single hop, i.e., in the same link that they were transmitted. When two interfaces do not participate in the same link, packets between them need to be routed across the network by intermediate computers, that is, sent from the link in which they were first transmitted to a link in which they are received by their destination.
Computers able to perform such forwarding operation between different links are called routers (or intermediate systems), and those that process information as senders or final receivers are called hosts (or end systems). Computers can behave simultaneously as hosts and routers as far as they have interfaces attached to (at least) two links and are able to make forwarding decisions [116].
Therefore, communication between interfaces that do not participate in the same link (indirect communication) requires the following additional conditions:
(iii) in case they have multiple interfaces, hosts must be able to determine to which interface (and thus, to which router) packets need to be sent.
(iv) routers must be able to forward packets to their final destination, if there is a link to it, or to a router that is closer 3 to the final destination.
Equivalently, hosts and routers in a network must be able, for any packet, to deliver it to a link to which its destination is attached, or to determine the next hop towards its destination. The maps between possible destinations and next hops are called routing tables. In case of hosts, the routing table indicates as next hops routers that are reachable through each of the available interfaces. Routing tables from hosts and routers also contain information about the links to which they are able to deliver (and forward, in case of routers) packets. Information collected in the set of routing tables enables thus the communication between computers with interfaces not attached to a common link; such information is maintained and updated in the routers by way of a routing protocol.
For stable networks that contain a small number of hosts and routers, routing tables can be filled and maintained manually, with human operation (static routing). As the network grows, and changes in the topology are more frequent (for instance, due to router failures), routing tasks become more complex and dynamic routing protocols are needed.
Definition 1.10 ( Routing protocol ). A routing protocol is a set of procedures performed over the network in order to collect routes and maintain the routing tables of the routers in the network, so that they enable computers to transmit and successfully deliver packets to every possible destination in the network.
There are two main approaches to dynamic routing:
• Proactive routing. Routers collect topology information from the network and maintain proac-tively (i.e., regardless on whether they are used) routes towards all destinations. This way, routers are able to forward packets at any time to any destination in the network. Depending on how the information for such forwarding decisions is acquired, three approaches can be distinguished:
– Link state routing. Routers advertise the status of their links (link-state) to the whole network. This way, every router in the network receives the link-state of other routers in the network, maintains information about the whole network topology and is therefore able to locally compute network-wide shortest paths, usually by way of Dijkstra’s algo-rithm [135]. Examples of this approach are the Open Shortest Path First (OSPF, RFCs 2328 and 5340 [107, 28]) and the Intermediate System to Intermediate System (IS-IS, RFC 1142 [122]) protocols, as well as the Optimized Link State Routing protocol (OLSR, RFC 3626 [71]). OSPF and IS-IS are described in more detail in chapter 10.
– Distance-vector routing. A router shares its routing table only with its neighbors, indicat-ing its distance and the next hop towards any reachable destination. Neighbor distance is defined according to the current link metric, which assigns a scalar cost to any available link in the network. By receiving the routing tables of all its neighbors, which in turn have been shared with the neighbors of the neighbors, a router is able to identify, for each advertised destination, the neighbor that provides shortest distance and select it as next hop. Distance-vector protocols mostly use the distributed Bellman-Ford algorithm [136, 133] to identify network-wide shortest paths. The Routing Information Protocol (RIP, RFCs 1058 [124], 2080 [110] and 2453 [102]) is a prominent example of this family.
– Path-vector routing. Based on the same principle as distance-vector routing, a router advertises to its neighbors the paths to all reachable destinations. Each path is described by indicating the routers that are traversed. This way, local distribution of locally main-tained paths enables all routers in the network to build routes to all possible destinations. The most prominent example of this family of protocols is the Border Gateway Protocol (BGP, RFC 1771 [117]).
• Reactive routing. A router calculates routes to a destination only when it receives information addressed to that destination and it is not known (i.e., the routing table does not provide a next hop). Dynamic Source Routing (DSR, RFC 4728 [38]) or Ad hoc On-Demand Distance Vector (AODV, RFC 3561 [75]) are examples of reactive routing protocols.
The main advantage of proactive algorithms when compared to reactive algorithms is that all routes are immediately available for proactive routers when the network has converged, which reduces the delay for data traffic with respect to reactive routing protocols. Such immediate avail-ability of routes requires, however, that topology information is flooded periodically over the network and independently from the data traffic load.
Among proactive algorithms, distance-vector and link-state are the main types of algo-rithms [100] – path-vector algorithms being a variation of distance-vector. Distance-vector protocols were used in the early stages of computer networking, but were replaced gradually by link-state protocols in the Internet. The reasons for this replacement were the existence of problems in distance-vector algorithms, in particular the well-known count-to-infinity problem [70] (which does not appear on path-vector protocols), as well as the poor scalability and slow convergence properties of distance-vector with respect to link-state algorithms [98, 100].
Convergence time differences between distance-vector and link-state can be observed by looking at the way to advertise the failure of a link over the network. In distance-vector algorithms, once a router detects such a failure, it updates the cost of its route towards the lost neighbor and sends its new distance-vector to its neighbors. Neighbors receive this update and recompute the cost of the affected route, and then transmit in turn their new distance-vectors. Propagation of topology changes is thus slower than in link-state algorithms, in which a router detecting the failure of the link towards one of its neighbors floods an updated topology description which is directly forwarded over the network, without delays caused by route re-computation in intermediate routers [100, 127].
Connecting Networks
Condition (ii) of section 1.3 states that the information exchange within a computer net-work requires that the involved interfaces of the corresponding computers agree on the formats and procedures to communicate. Given the existence of different network technologies4 – and, therefore, different sets of formats and procedures for communication within networks, the question arises on how to connect different networks (that may use different families of communication protocols) and how to enable communication between computers (interfaces) not in the same network.
The Internet Protocol (IP, RFC 791 [128]) provides such ability to exchange information between interfaces belonging to interconnected networks. These interconnected networks are called internetworks.
Definition 1.11 ( Internetwork ). An internetwork is a computer network (in the sense of def. 1.1) that results from connecting already existing computer networks. Such computer networks may be based on different network technologies.
IP enables communication in internetworks mainly by way of two elements: (a) a common addressing model for interfaces, the IP addressing model, and (b) an additional abstraction layer that permits treating links from different network technologies as IP links. Both concepts (IP addressing model and IP link) are presented in section 1.4.1.
IP is the main protocol for internetworking and one of the base protocols of the architec-ture of the biggest internetwork in the world, the Internet. The architecture of internetworks and, in particular, the Internet, is discussed in section 1.4.2, and the Internet routing architecture is detailed in section 1.4.3. Due to its popularity, IP has become a standard protocol not only within internetworks, but also for networks based on a single network technology.
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
