text:
Communication Networks/Wireless Internet

Introduction
The ability to communicate with the rest of the world instantaneously has been the ultimate goal for the design of network communication system. For such a large coverage, it seems only realistic and achievable through wireless networks. This becomes the driving force of all the wireless network research done all over the world.

After the huge success of Internet, IEEE came up with the protocols for Wireless Networks. In this chapter, we will study the IEEE 802.11 standards, and the different types of wireless networks.

There are 2 different protocols that are prominent in the field of wireless internet: WiFi and WiMAX.

Basics in Wireless WiFi
A wireless LAN (WLAN) is a set of network components connected by electromagnetic (radio) waves instead of wires. WLANs are used in combination with or as a substitute to wired computer networks, adding flexibility and freedom of movement within the workplace. Wireless LAN clients enjoy great mobility and can access information on the company network or even the Internet from the store, boardroom or throughout the campus without relying on the availability of wired cables and connections.

The proposed standard 802.11 works in two modes:

1. In the presence of base station.

2. In the absence of base station

In first case all communication goes through the base station known as the access point in 802.11 terminologies. This is known as infrastructure mode. In latter case, the computers just communicate with each other directly this mode is called as ad hoc networking.

IEEE 802.11 denotes set of wireless LAN/WLAN standards developed by IEEE standards working committee (IEEE 802). Some of the many challenges that had to be met where :finding a suitable frequency band that was available, preferably worldwide; dealing with the fact that radio signals have a finite range; ensuring users privacy and security; worrying about human safety; and finally, building a system with enough bandwidth to be economically feasible.

At the time of standardization process it was decided that 802.11 be made compatible with Ethernet above data link layer. But several inherent differences exist and had to be dealt with by the standard.

First, a computer on Ethernet always listens to the ether before transmitting. In case of wireless LANs this is not possible. It may happen that the range of a station may not be able to detect the transmission taking place between other two stations resulting in collision.

The second problem that had to be solved is that radio signals can be reflected off the solid objects, so it may be received multiple times. This interference results in Multipath fading.

The third problem is that if a notebook computer is moved away from base station to another there must be some way of handing it off.

After some work the committee came up with a standard that addressed these and other concerns. The most popular amendments are 802.11a, 802.11b and 802.11g to original standard. The security was also enhanced by amendment 802.11i.The other specifications from (c-f, h, j) are service enhancements and extensions

The Electromagnetic Spectrum
The industrial, scientific and medical (ISM) radio bands were originally reserved internationally for non-commercial use of RF electromagnetic fields for industrial, scientific and medical purposes

Figure 3.1 The Electromagnetic Spectrum

As the figure shows the ISM band is shared by license free communication application such as wireless LANs and Bluetooth. IEEE 802.11 b/g wireless Ethernet operates on 2.4 GHz band. Although these devices share ISM band they are not part of ISM devices. Due to the ISM Band which includes Bluetooth, microwave oven and cordless telephones the 802.11b and 802.11g equipment have to sustain interference. This is not the case with 802.11a since it uses 5 GHz band

Comparison between three unlicensed bands:

IEEE 802.11 Standards / WiFi
Wifi simply stands for Wireless Fidelity.

The services and protocols of 802.11 maps to lower two layers of OSI reference model. The protocols used by all 802 variants have a certain commonality of structure. The partial view of protocol stack is shown in figure 3.2. The data link layer is split into two sub layers. The MAC (Medium access control) sub layer is responsible for allocation of channels and also determines who transmits next. The function of Logic Link Layer is to hide the differences between different 802 variants.

Figure 3.2 Protocol Stack 802.11

The 802.11 standard initially specified three transmission techniques. The infrared method which uses the same technology as television remote controls do. The other two methods use short radio and are called as FHSS and DSSS. Both of these don't require licensing. In 1999 two new techniques were introduced to achieve higher bandwidth. These are called as OFDM and HR-DSSS. They operate at up to 54 Mbit/s and 11 Mbit/s respectively.

Each of the five permitted transmission techniques makes it possible to send a MAC frame from one station to another. They differ in technology used and speed achievable. Let’s have a look at them one by one:

Infrared option used diffused transmission at .85 or .95 microns. Two speeds are permitted: 1 Mbit/s and 2 Mbit/s. A technique called as Gray encoding is used for 1 Mbit/s. In this scheme a group of 4 bits is encoded as a 16 bit codeword containing 15 zeros and single 1. At 2 Mbit/s the encoding takes 2 bits and produces 4 bit codeword. Infrared cannot penetrate from walls hence two cells are well isolated from each other. Nevertheless due to low bandwidth this is not the popular option.

FHSS (Frequency Hopping Spread Spectrum) uses 79 channels each 1 MHz wide starting at the low end of 2.4-GHz ISM band. A pseudorandom number generator is used to produce sequence of frequencies hopped to. The only condition is the seed to random number must be known by both and synchronization must be maintained. The amount of time spend at each frequency is known as Dwell Time and must be less than 400 ms. The two main advantages of FHSS are Security offered due to hopping sequence and resistance to Multipath fading. The main disadvantage is low bandwidth.

Figure 3.3 Frequency Hopping Spread Spectrum

Direct Sequence Spread Spectrum (DSSS) is also restricted to 2 Mbit/s. In this method a bit is transmitted as 11 chips using Barker sequence. It uses Phase shift Modulation at 1 Mbaud transmitting 1 bit per baud when transmitting at 1 Mbit/s and 2 Mbaud when transmitting at 2 Mbit/s.

Orthogonal Frequency Division Multiplexing (ODFM), used by 802.11a, is the first of the sequence of high speed wireless LANs. It delivers the speed of up to 54 Mbit/s operating at 5 GHz ISM. As the term suggests different frequencies are used, in all 52, 48 for data and 4 for synchronization. Phase shift modulation is used for speed up to 18 Mbit/s and QAM is used after that.

High Rate Direct Sequence Spread Spectrum (HR-DSSS), 802.11b, is another spread spectrum technique, which used 11 million chips per second to achieve 11 Mbit/s in the 1.4 GHz Band. The data rates supported by 802.11 are 1, 2, 5.5, and 11 Mbit/s. The two slow rates run at 1 Mbaud, with 1 and 2 bits per Baud, respectively using Phase shift modulation. The two faster rates run at 1.375 Mbaud, with 4 and 8 bits per Baud respectively, using Walsh/Hadamard codes. In practice operating speed of 802.11b is nearly always 11 Mbit/s. Although 802.11b is slower than 802.11a the range is about 7 times that of 802.11a, which is considered more significant in many situations.

An enhanced version of 802.11b, 802.11g, uses OFDM modulation method of 802.11a but operates in the narrow 2.4 GHz ISM band along with 802.11b. It operates up to speed of 54 Mbit/s. To conclude the 802.11 committee has produced three different high speed wireless LANs (802.11a, 802.11b, 802.11g) and three low speed wireless LANs

 802.11 Data Frame Structure  The 802.11 standard define three different standards of frames on wire: data, control and management. Each of these has a header with variety of fields within MAC sub layer. The format of data frame is shown in figure. Following is the brief description of each:

Figure 3.4 802.11 Frame Structure

First is the Control field which has 11 subfields. The first of these is protocol version, which allows two versions of protocols to operate at the same time. Then comes the type field, which can be data, control or management. The subtype contains RTS or CTS. The To DS and From DS fields indicate whether the frame is going to or coming from intercell distribution. MF indicates more fragments follow. Retry means retransmission of frame sent earlier. Power management bit is used by base station to save power by putting the receiver to sleep or taking out of sleep state. More bit indicate that sender has more frames for receiver. W bit specifies that the frame body has been encrypted using WEP (Wired Equivalent Privacy) algorithm O bit indicates the sequence of bits needs to be processes in strict order. The Duration field indicates how long the channel will be occupied by the frame. This field is also contained in control frames. The frame header contains four addresses all in standard IEEE 802 format. First two addresses are for the source and destination other two are for source and destination of base station

Address 1: All stations filter on this address. Address 2: Transmitter Address (TA), Identifies transmitter to address the ACK frame to. Address 3: Dependent on To and From DS bits. Address4: Only needed to identify the original source of WDS (Wireless Distribution System) frames.

Sequence field allows fragments to be numbered. 12 bits identify the frame and 4 identify the fragment. The Data field can contain payload of up to 2312 bytes, followed by Checksum. Management frames have a format similar to data frames. The only difference is they don't have the base station address, because management frames are restricted to single address. Control frames are shorter having at the most two addresses with no data or sequence field.

IEEE 802.11 Architecture
The emergence of wireless networks as a communication channel allows seamless connectivity between different electronic devices. Based on the network structure, wireless networks can be divided into two classes: infrastructure-based and ad hoc. The infrastructure-based network is a pre-configured network that aims to provide wireless services to users in a fixed network area. On the other hand, the ad hoc network has no fixed infrastructure so that a network can be established anywhere to offer services to users.

 Infrastructure Mode

The current existing wireless networks are mostly infrastructure-based, such as cellular networks and IEEE 802.11 wireless LANs. In a cellular network, whole service areas are divided into several small regions called cells. There is at least one base station to provide services to devices (i.e. cellular phone) in each cell. Each device connects to the network by establishing a wireless connection to the base station in order to transmit and receive packets. The base stations are connected through high bandwidth wired connections to exchange packets, making it possible for senders and receivers within different service areas to communicate. Note that all network traffic is constrained to either uplink (device to base station) or downlink (base station to device). Emphasis in this research area focuses on providing quality of service (QoS) guarantees, such as soft handoff to ensure a low probability of dropped call or no significant packet delay due to mobility of user from one cell to a neighboring cell. The drawback of this kind of network is its requirement for a fixed infrastructure, which is infeasible in certain situations. The ad hoc network is proposed to address this problem to allow network with infrastructureless architecture.

Figure 4.1 A Small-scaled Model of a Wireless Infrastructure Network

 Ad-Hoc Mode

Unlike the conventional infrastructure-based wireless network, ad hoc network, as a distributed wireless network, is set of mobile wireless terminals communicating with each other without any pre-existing fixed infrastructure. The mobile ad hoc network has several unique features that challenge the network operation, such as the routing algorithm, Quality of Service (QoS), resource utilization, etc. The following figure depicts a small-scaled model of a wireless ad hoc network. All the terminals, also referred to as mobile nodes, exchange information among one another in a fully distributed manner through wireless connections within the ad hoc network. And due to the mobility of these nodes, the network topology is under constant changes without any centralized control in the system. These are several main concerns that needs to be considered when designing a specific application-layer protocol based on wireless ad hoc networks.

Figure 4.2 A Small-scaled Model of a Wireless Ad Hoc Network

802.11a
What is 802.11a and history of 802.11a?

It is a Wireless LAN standard from the IEEE(Institute of Electronics and Electrical Engineers). It was released on October 11 in 1999.

Speed:

It can achieve a maximum speed of 54Mbit/s. Although the typical data rate transfer is at 22Mbit/s. If there is a need the data rate will be reduced to 48, 36, 24, 18, 12, 9 then 6Mbit/s respectively. This usually occurs as the distance between the access point or the wireless router and the computer gets further and further away.

Frequency:

It operates under the 5GHz frequency band. The advantage of this is that it has lesser interference compared to the 802.11b and 802.11g standards, which operate at 2.4GHz. It means that quite a number of electronic equipment use this frequency band such as microwaves, cordless phones, bluetooth devices etc. Therefore, the more electronic equipment that use the same frequency band, the more interferences it will cause among the equipment that are using that frequency band.

Interoperability:

802.11a will not operate readily with 802.11b or 802.11g due to the different frequency bands unless the equipment implements the both standards. E.g. Equipment that use both 802.11a and 802.11g standards.

Number of Channels

It has 12 non-overlapping channels. 8 are for indoor(within the area) and the other 4 are for point to point.

802.11b
What is 802.11b and its history

It is also something like 802.11a. It is of course a wireless standard made by IEEE and guess what it was implemented on the same month and year as 802.11a which was in October 1999.

Speed

802.11b has the lowest speed after 802.11 legacy. It can reach a maximum speed of only 11 Mbit/s.

Frequency

Wireless LANs Issues (CSMA/CA)
At the MAC sublayer, IEEE 802.11 uses the carrier sense multiple access with collision avoidance (CSMA/CA) media access control (MAC) protocol, which works in the following way:

• A wireless station with a frame to transmit first listens on the wireless channel to determine if another station is currently transmitting (carrier sense). If the medium is being used, the wireless station calculates a random backoff delay. Only after the random backoff delay can the wireless station again listen for a transmitting station. By instituting a random backoff delay, multiple stations that are waiting to transmit do not end up trying to transmit at the same time (collision avoidance). The CSMA/CA scheme does not ensure that a collision never takes place and it is difficult for a transmitting node to detect that a collision is occurring. Additionally, depending on the placement of the wireless access point (AP) and the wireless clients, a radio frequency (RF) barrier can prevent a wireless client from sensing that another wireless node is transmitting. This is known as the hidden station problem, as illustrated in Figure 5.1(a).

Figure 5.1 (a)Hidden Station Problem   (b)Exposed Station Problem

Hidden Station Problem: Wireless stations have transmission ranges and not all stations are within radio range of each other. Simple CSMA will not work! A transmits to B. If C “senses” the channel, it will not hear A’s transmission and falsely conclude that C can begin a transmission to B.

Exposed Station Problem: This is the inverse problem. C wants to send to D and listens to the channel. When C hears B’s transmission to A, C falsely assumes that it cannot send to D. This reduces network efficiency.

Multiple Access with Collision Avoidance
To provide better detection of collisions and a solution to the hidden station problem, IEEE 802.11 also defines the use of an acknowledgment (ACK) frame to indicate that a wireless frame was successfully received and the use of Request to Send (RTS) and Clear to Send (CTS) messages. When a station wants to transmit a frame, it sends an RTS message indicating the amount of time it needs to send the frame. The wireless AP sends a CTS message to all stations, granting permission to the requesting station and informing all other stations that they are not allowed to transmit for the time reserved by the RTS message. The exchange of RTS and CTS messages eliminates collisions due to hidden stations.

For example, the idea is to have a short frame transmitted from both sender and receiver before the actual transfer. As shown in Figure 5.2, A sending a short RTS (30 bytes) to B with length of L. B responding with a CTS to A. And whoever hears CTS shall remain silent for the duration of L. Then A can safely send data (length L) to B.

Figure 5.2 An illustration of Multiple Access with Collision Avoidance

Medium Access Control
 Distributed Coordination Function (DCF) is the fundamental MAC technique of the IEEE 802.11 wireless LAN standard. DCF employs a distributed CSMA/CA distributed algorithm and an optional virtual carrier sense using RTS and CTS control frames.

DCF mandates a station wishing to transmit to listen for the channel status for a DIFS interval. If the channel is found busy during the DIFS interval, the station defers its transmission or proceeds otherwise. In a network that a number of stations contend for the multi-access channel, if multiple stations sense the channel busy and defer their access, they will also find that the channel is released virtually simultansously and then try to seize the channel. As a result, collisions may occur. In order to avoid such collisions, DCF also specifies random backoff, which is to force a station to defer its access to the channel for an extra period. The length of the backoff period is determined by the following equation:

$$Backoff Time = random \times aSlotTime$$

DCF also has an optional virtual carrier sense mechanism that exchanges short Request-to-send (RTS) and Clear-to-send (CTS) frames between the source and destination stations between the data frame is transmitted. This is illustrated in Figure 5.3 below. C (in range of A) receives the RTS and based on information in RTS creates a virtual channel busy NAV(Network Allocation Vector). And D (in range of B) receives the CTS and creates a shorter NAV.

Figure 5.3 The use of virtual carrier sensing using CSMA/CA

DCF also includes a positive acknowledge scheme, which means that if a frame is successfully received by the destination it is addressed to, the destination needs to send an ACK frame to notify the source of the successful reception. DCF is defined in subclause 9.2 of the IEEE 802.11 standard and is de facto default setting for WiFi hardware.

 Fragmentation is a technique to improve network throughput. Due to unreliable ISM band causing high wireless error rates, long packets have less probability of being successfully transmitted. So the solution is to implement MAC layer fragmentation with stop-and-wait protocol on the fragments, as shown in figure below.

Figure 5.4 Fragmentation in 802.11 for better throughput

IEEE 802.11 standard also has an optional access method using a Point Coordination Function (PCF). PCF allows the Access Point (PC) acting as the network coordinator to manage channel access.

 Point Coordination Function (PCF) is a Media Access Control (MAC) technique use in wireless networks which relies on a central station, often an Access Point (AP), to communicate with a node listening, to see if the airwaves are free (i.e., all other stations are not communicating). PCF simply uses the AP as a control system in wireless MAC. PCF seems to be implemented only in very few hardware devices as it is not part of the Wi-Fi Alliance's interoperability standard.

Since most APs have logical bus topologies using shared circuits, only one message can be processed at one time because it is a contention based system. Therefore, a media access control technique is required.

The problem with wireless is the hidden station problem, where some regular stations (which communicate only with the AP) cannot see other stations on the extreme edge of the geographical radius of the network (because the wireless signal attenuates before it can reach that far). Thus having an AP in the middle allows the distance to be halved, allowing all station to see the AP and consequentially have the maximum distance between two stations on the extreme edges of a circle-star topology (in a circled-star physical topology).

Co-Existence between distributed DCF and centralized PCF is possible using InterFrame Spacing as illustrated in Figure 5.5 below.

• SIFS (Short IFS) :: is the time waited between packets in an ongoing dialog (RTS,CTS,data, ACK, next frame)

• PIFS (PCF IFS) :: when no SIFS response, base station can issue beacon or poll.

• DIFS (DCF IFS) :: when no PIFS, any station can attempt to acquire the channel.

• EIFS (Extended IFS) :: lowest priority interval used to report bad or unknown frame.

Figure 5.5 Interframe Spacing in 802.11

IEEE 802.11 AP Services
The 802.11 AP service include two types of services:

1. Distribution services: The distribution services include many functionalities such as association - which is related to a particular station that reports identity, data rate,and power; disassociation, reassociation which is like a handover of controls, distribution using the routing protocols, and integration.

2. Intracell services: The intracell services include different functions such as authentication, deauthentication, privacy, and data deliver. Authentication is a process to authenticate the user once the association takes place. It is always conducted after association with an AP. The privacy is a wired equivalent privacy. More information on wireless security will be discussed later.

Lets take a look in detail how each of this process works.

Association Process: The association with an AP takes place in the following way -

When a Client comes on line, it will broadcast a Probe Request. An AP that hears this will respond with details. The client makes a decision who to associate with based on the information returned from the AP. Next the Client will send an authentication request to the desired AP. The AP authenticates the client, and sends an acknowledge back. Next the client sends up an association request to that AP. The AP then puts the client into the table, and sends back an association response. From that point forward, the network acts like the client is located at the AP. The AP acts like an Ethernet hub.

Re-association Process: When the client wants to associate back with the AP which was involved in the prior communication, re-association takes place. The process takes place in the following way - As the client is moving out of range of his associated AP, the signal strength will start to drop off. At the same time, the strength of anther AP will begin to increase. At some point in time, BEFORE communication is lost, the client will notify AP A that he is going to move to AP B. B and A will also communicate to assure any information buffered in A get to B over the backbone. This eliminates retransmitting packets over the air, and over the backbone. The same handoff can occur if the load on A become large, and the client can communicate with someone other than A.

Cellular and 802.11b

There are quite a few differentiating functionalities in both of these services. Lets see how these two communication protocols differ.

Bluetooth

Bluetooth is a radio standard; a technology by which phones, computers, and personal digital assistants(PDAs), can be easily interconnected using a short-range wireless connection. Following are some of the features of Bluetooth technology:

IEEE 802.11 Security
This is a new section that is introduced in this chapter. The contents are based on my understanding and prior work experience in embedded wireless technology field.

Wireless Security

After the emergence of 802.11 it was certain that the internet technology was no longer going to be the same. Many new protocols and communication devices were introduced. To communicate using these devices, and to be secure over the internet, it was going to be a new challenge. The wireless security was developed in such a way that both the tasks were accomplished - hence no interference and secured wireless connection. There are different types of wireless security involved which will be discussed in brief. Let us see the different wireless security features available currently.

1. WPA and WPA2:

Wi-Fi Protected Access (WPA and WPA2) is a class of systems to secure wireless Wifi, computer networks. It was created in response to several serious weaknesses researchers had found in the previous system, Wired Equivalent Privacy (WEP). WPA2 implements the full standard, but will not work with some older network cards. Both provide good security, with two significant issues:

•	either WPA or WPA2 must be enabled and chosen in preference to WEP. WEP is usually presented as the first security choice in most installation instructions.

•	in the "Personal" mode, the most likely choice for homes and small offices, a passphrase is required, for full security, it must be longer than the typical 6 to 8 character passwords users are taught to employ.

2. WEP:

Wired-Equivalent Privacy (WEP) protocol. A security protocol, specified in the IEEE 802.11 standard, that attempts to provide a wireless LAN (WLAN) with a minimal level of security and privacy comparable to a typical wired LAN. WEP encrypts data transmitted over the WLAN to protect the vulnerable wireless connection between users (clients) and access points (APs). WEP is weak and fundamentally flawed.

EAP in Wireless Technology In addition to these standards, wireless security also involves additional authentication protocol known as Extensible Authentication Protocol (EAP).

Extensible Authentication Protocol, or EAP, is a universal authentication framework frequently used in wireless networks and Point-to-Point connections. It is defined by RFC 3748. Although the EAP protocol is not limited to wireless LAN networks and can be used for wired LAN authentication, it is most often used in wireless LAN networks. Commonly used modern methods capable of operating in wireless networks include EAP-TLS, EAP-SIM, EAP-AKA, PEAP, LEAP and EAP-TTLS.

IEEE 802.22
With the continuous move to the digital, it becomes not only possible to compress signals but to take full advantage of a channel's capability. Tests of the IEEE 802.22 as a solution to make use of spare radio spectrum that become available with the move to Digital Terrestrial TV (DTV), including the so called White Space that exists between each DTV data channel, that is left free due to the possibility of interference have been going on for some time in the EU the move to digital TV is expected to be concluded by 2012. The possibility to utilize this unused spectrum would permit to deploy Internet coverage in even remote locations at very attractive prices.

Summary
802.11 dominates the field of Wireless LANs. The IEEE 802.11 committee came up with various standards which use different technology and achieve variable speeds. Its physical layer allows five different transmission modes which include infrared, spread spectrum and multi channel FDM system.

Wireless LANs have their own problem and solution. The biggest one is caused by hidden stations. To deal with this problem 802.11 supports two model of operation, the first one is called as DSF (Distributed Coordination Function) and the other PCF (Point Coordination Function). When DSF is employed 802.11 uses CSMA/CA. Distributed DCF and centralized PCF can also co–exist using InterFrame Spacing.

The 802.11 AP service include two types of services distribution services which include association, disassociation and reassociation and Intracell services which include different functions such as authentication, deauthentication, privacy, and data deliver.

Wireless Security plays an important role in current wireless technology. One should not overlook the features involved in wireless networks. The standards such as WPA, WEP, EAP, TKIP are the fundamentals of wireless security now.

Questions
Q: What are IEEE 802.11a, 802.11b and 802.11g?

A: IEEE 802.11a, 802.11b and 802.11g are industry standard specifications issued by the Institute of Electrical and Electronic Engineers (IEEE). These specifications define the proper operation of Wireless Local Area Networks (WLANs). 802.11a—an extension to 802.11 that applies to wireless LANs and provides up to 54 Mbit/s in the 5 GHz band. 802.11a uses an orthogonal frequency division multiplexing encoding scheme rather than FHSS or DSSS. 802.11b—an extension to 802.11 that applies to wireless LANS and provides 11 Mbit/s transmission (with a fallback to 5.5, 2 and 1 Mbit/s) in the 2.4 GHz band. 802.11b uses only DSSS. 802.11b was a 1999 ratification to the original 802.11 standard, allowing wireless functionality comparable to Ethernet. 802.11g—applies to wireless LANs and provides 20+ Mbps in the 2.4 GHz band.

Q: When do we need an Access Point?

A: Access points are required for operating in infrastructure mode, but not for ad-hoc connections. A wireless network only requires an access point when connecting notebook or desktop computers to a wired network. If you are not connecting to a wired network, there are still some important advantages to using an access point to connect wireless clients. First, a single access point can nearly double the range of your wireless LAN compared to a simple ad hoc network. Second, the wireless access point acts as a traffic controller, directing all data on the network, allowing wireless clients to run at maximum speed.

Q: How many simultaneous users can a single access point support?

A: There are two limiting factors to how many simultaneous users a single access point can support. First, some access point manufacturers place a limit on the number of users that can simultaneously connect to their products. Second, the amount of data traffic encountered (heavy downloads and uploads vs. light) can be a practical limit on how many simultaneous users can successfully utilize a single access point. Installing multiple access points can overcome both of these limitations.

Q: Why do 802.11a WLANS operate in the 5 GHz frequency range?

A: This frequency is called the UNII (Unlicensed National Information Infrastructure) band. Like the 2.4 GHz ISM band used by 802.11b and 802.11g products, this range has been set aside by regulatory agencies for unlicensed use by a variety of products. A major difference between the 2.4 GHz and 5 GHz bands is that fewer consumer products operate in the 5 GHz band. This reduces the chances of problems due to RF interference.


text:
Communication Networks/ARP

= Address Resolution Protocol = Address Resolution Protocol (ARP) is a mechanism used by IP to find the hardware address of a host from an IP address.

When IP is trying to send a datagram to the Data Link Layer (layer 2), Ethernet will be informed to look for the hardware address, also known as MAC Address, of the destination in the local network. Since Ethernet is using hardware addresses to identify source and destination, ARP will be used to obtain the hardware address by broadcast the specified IP address. Then, the machine that matched the specified IP address will reply with the requested hardware address.

Figure 9: ARP broadcast

ARP Packet Format
Similar to IP Packet, Each ARP packet field is explain as follows:

Figure 10: ARP packet

The image below is a snapshot of an ARP packet capture on Ethereal:

Figure 11: ARP packet captured from Ethereal

Notice the destination from Ethernet header is all 1s (ff:ff:ff:ff:ff:ff). ARP is performing a broadcast in the above trace.

Here is another example for ARP to locate hardware address. “arp –a” command allows to display current ARP cache tables for all interfaces:

Figure 12: ARP Command for Hardware Address

IP allows datagram to transport across a large network, the Internet. However, if two nodes are going to communicate across the same Local Area Network (LAN), IP in layer 3 will not be needed because ARP with the Ethernet address is enough for the data transfer. Unless many different layer 2 communications are established across the internet, then IP and router will be forced to use. Layer 3 IP is usually only used when a communication goes beyond layer 2 and is required.

Summary
Address Resolution Protocol (ARP) is a mechanism used by IP that finds the hardware address of a host from an IP address within the local area network.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Communication Networks/ARP


text:
Communication Networks/Routing

Routing
Routing is the process of getting information packets where they need to go. Routing is a surprisingly complicated task, and there are a number of different algorithms used to find the shortest route between two points.

Introduction
IP addressing is based on the concept of hosts and networks. A host is essentially anything on the network that is capable of receiving and transmitting IP packets on the network, such as a workstation or a router. Routing is a process of moving data from one host computer to another. The difference between routing and bridging is that bridging occurs at Layer 2 (the link layer) of the OSI reference model, whereas routing occurs at Layer 3 (the network layer). Routing determines the optimal routing paths through a network.

Routing Algorithms
The routing algorithm is stored in the router's memory. The routing algorithm is a major factor in the performance of your routing environment. The purpose of the routing algorithm is to make decisions for the router concerning the best paths for data. The router uses the routing algorithm to compute the path that would best serve to transport the data from the source to the destination. Note that you do not directly choose the algorithm that your router uses. Rather, the routing protocol you choose for your network determines which algorithm you will use. For example, whereas the routing protocol Routing Information Protocol (RIP) may use one type of routing algorithm to help the router move data, the routing protocol Open Shortest Path First (OSPF) uses another. The routing algorithm cannot be changed. The only way to change it is to change routing protocols. The overall performance of your network depends mainly on the routing algorithm, so you should research the algorithms each protocol uses before deciding which to implement on your network. There are two major categories of routing algorithms - distance vector or link-state. Every routing protocol named "distance vector" uses the distance vector algorithm, and every link-state protocol uses the link-state algorithm.

Routing Algorithms within Routing Protocols
One of the jobs of the routing protocol is to provide the information needed by the routing algorithm to compute its decisions. This is the point where many protocols differ. The information provided to the algorithm can be different from protocol to protocol.

The routing protocol gathers information about networks and routers from the surrounding environment and stores the information within a routing table in the router's memory. The routing algorithm is run using the information within this table to calculate the best path from one network to another. Calculating the new values within the formula then generates a sum. The result of this calculation is used then to determine where to send information. For example, the table below illustrates a sample routing table for a fictitious routing environment. The information that is passed to the routing algorithm within the routing table is gathered by the routing protocol through a process known as a routing update. Through a series of updates, each router will tell the other what information it has. Eventually, an entire routing table will be built.

The sample routing algorithm states that the best path to any destination is the one that has the lowest metric value. A metric is a number that is used as a standard of measurement for the links of a network. Each link is assigned a metric to represent anything from monetary cost to use the line, to the amount of available bandwidth. When Router A is presented with a packet bound from Router C, the routing table shows two possible paths to choose from. The first choice is to send the packet from Router A directly over the link to Router C. The second option is to send the packet from Router A to Router B and then on to Router C. The routing algorithm is used to determine which option is best.

Some routing protocols might only provide one metric to the routing algorithm, whereas others might provide up to ten. On the other hand, whereas two protocols might both send only one metric to the algorithm, the origin of that metric might differ from protocol to protocol. One routing protocol might give an algorithm the single metric of cost, but that cost could represent something different than another protocol using the same metric.

The algorithm in our example states that the best path is the one with the lowest metric value. Therefore, by adding the metric numbers associated with each possible link, we see that the route from Router A to Router B to Router C has a metric value of 5, while the direct link to Router C has a value of 6. The algorithm selects the A-B-C path and sends the information along.

Distance Vector Algorithms

A distance vector algorithm uses metrics known as costs in order to help determine the best path to a destination. The path with the lowest total cost is chosen as the best path.

When a router utilizes a distance vector algorithm, different costs are gathered by each router. These costs can be completely arbitrary numbers. Costs can also be dynamically gathered values, such as the amount of delay experienced by routers when sending packets over one link as opposed to another. All the costs are compiled and placed within the router's routing table and then they are used by the algorithm to calculate a best path for any given network scenario.

Although there are many resources that will offer complex mathematical representations of what distance vector algorithms are and how they compute their decisions, the core concept remains the same - by adding the metrics for every optional path on a network, you will come up with at least one best path. The formula for this is as follows:

M(i,k) = min [M(i,t) + M(t,k)]

This formula states that the best path between two networks (M(i,k)) can be found by finding the lowest (min) value of paths between all network points. Let's look again at the routing information in the table above. Plugging this information into the formula, we see that the route from A to B to C is still the best path:

5(A,C) = min[2(A,B) + 3(B,C)]

Whereas the formula for the direct route A to C looks like this:

6(A,C) = min[6(A,C)]

This example shows how distance vector algorithms use the information passed to them to make informed routing decisions. The algorithms used by routers and routing protocols are not configurable, nor can they be modified.

Another major difference between distance vector algorithms and link state protocols is that when distance vector routing protocols update each other, all or part of the routing table (depending on the type of update) is sent from one router to another. By this process, each router is exposed to the information contained within the other router's tables, thus giving each router a more complete view of the networking environment and enabling them to make better routing decisions. Examples of distance vector algorithms include RIP and BGP, two of the more popular protocols in use today. Other popular protocols such as OSPF are examples of protocols which use the link state routing algorithm. Distance vector algorithms are also known as Bellman-Ford routing algorithms and Ford-Fulkerson routing algorithms. In these algorithms, each router has a routing table which shows it the best route for any destination. A typical graph and routing table for router J is shown below.

The table shows that if router J wants to get packets to router D, it should send them to router H first. When the packets arrive at router H, the current router checks its own table and makes a decision how to send the packets to D. In distance vector algorithms, each router has to follow the following steps:

1. It counts the weight of the links directly connected to it and saves the information to its table.

2. In a particular period of time, the router sends its table to its neighbor routers (not to all routers) and receives the routing table of each of its neighbors.

3. Based on the information the router receives from its neighbors' routing tables, it updates its own.

Let's consider one more example (the figure represented below).

The cost of each link is set to 1. Thus, the least cost path is simply the path with the fewer hops. The table below represents each node knowledge about the distance to all other nodes:

Initially, each node sets a cost of 1 to its directly connected neighbors and infinity to all the other nodes. Below is shown the initial routing table at node A:

During the next step, every node sends a message to its directly connected neighbors. That message contains the node's personal list of distances. Node F, for example, tells node A that it can reach node G at cost of 1; node A also knows that it can reach F at a cost of 1, so it adds these costs to get the cost of reaching G by means of F. Because 2 is less than the current cost of infinity, node A records that it can reach G at a cost of 2 by going trough F. Node A learns from C that node B can be reached from C at a cost of 1, so it concludes that the cost of reaching B via C is 2. Because this is worse than the current cost of reaching B, which is 1, the new information is ignored. The final routing table at node A is shown below:

The process of getting consistent routing information to all the nodes is called convergence. The final set of costs from each node to all other nodes is shown in the table below:

The cost of each link is set to 1. Thus, the least cost path is simply the path with the fewer hops.

One of the problems with distance vector algorithms is called "count to infinity." Let's examine the following problem with an example:

Consider a network with a graph as shown below. There is only one link between D and the other parts of the network.

with vectors

d [A][A] = 0     d [A][B] = 1     d [A][C] = 2       d [A][D] = 3

Now the C to D link crashes So cost [C][D] = ∞ C used to forward any packets with address D directly on the CD link, but now link is down, so C has to recompute its distance vector (and make a new choice of how to forward packets to D) - similarly D has to update its vector. After updating their vectors at C and D, we have

C views B as the best route to D, with cost 1 + 2, so C sends new vector to B. B learns that its former choice for sending to D via C now has higher cost, so B should recompute its vector.

View of B is that routing to D can either go via A or C with equal cost - B sends updated vector. Both A and C get updated vector from B and learn that their preferred route to D now has higher cost, so they recompute their own vectors.

Then A and C send their vectors, B has to update its vector again, sending another round to A and C, obtaining.

Notice that the routing table is very slowly converging to the fact that

d [x][D] = ∞ for x = A or x = B or x = C

This process loops until all nodes find out that the weight of link to D is infinity. In this way, experts say that distance vector algorithms have a slow convergence rate. In conclusion, distance vector algorithm is not robust. One way to solve this problem is for routers to send information only to the neighbors that are not exclusive links to the destination. For example, in this case, B should not send any information to C about D, because C is the only way to D.

Link-State Algorithms

Distance vector algorithms and link-state algorithms both favor the path with the lowest cost. However, link-state protocols work in more localized manner. Whereas a router running a distance vector algorithm will compute the end-to-end path for any given packet, a link-state protocol will compute that path as it relates to the most immediate link. That is, where a distance vector algorithm will compute the lowest metric between Network A and Network C, a link-state protocol will compute it as two distinct paths, A to B and B to C. This process is very efficient for larger environments. Link-state algorithms enable routers to focus on their own links and interfaces. Any one router on a network will only have direct knowledge of the routers and networks that are directly connected to it (or, the state of its own links). In larger environments, this means that the router will use less processing power to compute complicated paths. The router simply needs to know which one of its direct interfaces will get the information where it needs to go the quickest. The next router in line will repeat the process until the information reaches its destination. Another advantage to such localized routing processes is that protocols can maintain smaller routing tables. Because a link-state protocol only maintains routing information for its direct interfaces, the routing table contains much less information than that of a distance vector protocol that might have information for multiple routers. Like distance vector protocols, link-state protocols require updates to share information with each other. These routing updates, known as Link State Advertisements (LSAs), occur when the state of a router's links changes. When a particular link becomes unavailable (changes state), the router sends an update through the environment alerting all the routers with which it is directly linked.

In Link-State Algorithms, every router has to follow these steps:

1. Identify the routers that are physically connected to them and get their IP addresses When a router starts working, it first sends a "HELLO" packet over network. Each router that receives this packet replies with a message that contains its IP address.

2. Routers measure the delay time (or any other important parameters of the network, such as average traffic) for neighbor routers. In order to do that, routers send echo packets over the network. Every router that receives these packets replies with an echo reply packet. By dividing round trip time by 2, routers can count the delay time. The delay time includes both transmission and processing times - the time it takes the packets to reach the destination and the time it takes the receiver to process it and reply.

3. Broadcast its information over the network for other routers and receive the other routers' information. In this step, all routers share their knowledge and broadcast their information to each other. In this way, every router can know the structure and status of the network.

4. Routers use an appropriate algorithm to identify the best route between two nodes of the network. In this step, routers choose the best route to every node. They do this using an algorithm, such as the Dijkstra shortest path algorithm. In this algorithm, a router, based on information that has been collected from other routers, builds a graph of the network. This graph shows the location of routers in the network and their links to each other. Every link is labeled with a number called the weight or cost. This number is a function of delay time, average traffic, and sometimes simply the number of hops between nodes. For example, if there are two links between a node and a destination, the router chooses the link with the lowest weight.

Dijkstra algorithm
The Dijkstra algorithm goes through the following steps:

 * 1) The router builds a graph of the network. Then it identifies source and destination nodes, for example R1 and R2. The router builds then a matrix, called the "adjacency matrix." In the adjacent matrix, a coordinate indicates weight. [i, j], for example, is the weight of a link between nodes Ri and Rj. If there is no direct link between Ri and Rj, this weight is identified as "infinity."
 * 2) The router then builds a status record for each node on the network. The record contains the following fields:
 * 3) * Predecessor field - shows the previous node.
 * 4) * Length field - shows the sum of the weights from the source to that node.
 * 5) * Label field - shows the status of node; each node have one status mode: "permanent" or "tentative."
 * 6) In the next step, the router initializes the parameters of the status record (for all nodes) and sets their label to "tentative" and their length to "infinity".
 * 7) During this step, the router sets a T-node. If R1 is to be the source T-node, for example, the router changes R1's label to "permanent." Once a label is changed to "permanent," it never changes again.
 * 8) The router updates the status record for all tentative nodes that are directly linked to the source T-node.
 * 9) The router goes over all of the tentative nodes and chooses the one whose weight to R1 is lowest. That node is then the destination T-node.
 * 10) If the new T-node is not R2 (the intended destination), the router goes back to step 5.
 * 11) If this node is R2, the router extracts its previous node from the status record and does this until it arrives at R1. This list of nodes shows the best route from R1 to R2.

Dijkstra algorithm example:

Let’s find the best route between routers A and E. There are six possible routes between them (ABE, ACE, ABDE, ACDE, ABDCE, ACDBE), and it's obvious that ABDE is the best route because its weight is the lowest. But life is not always so easy, and there are some complicated cases in which we have to use algorithms to find the best route.

1. The source node (A) has been chosen as T-node, and so its label is permanent (permanent nodes are showed with filled circles and T-nodes with the -> symbol).

2. In this step, the status record of tentative nodes directly linked to T-node (B, C) has been changed. Also, because B has less weight, it has been chosen as T-node and its label has changed to permanent.

3. Like in step 2, the status records of tentative nodes that have a direct link to T-node (D, E), have been changed. Because router D has less weight, it has been chosen as T-node and its label has changed to permanent.

4. Because we do not have any tentative nodes, we just identify the next T-node. Because node E has the least weight, it has been chosen as T-node.

Now we have to identify the route. The previous node of E is node D, and the previous node of D is node B, and B's previous node is node A. So, we determine that the best route is ABDE. In this case, the total weigh is 4 (1+2+1). This algorithm works well, but it is so complicated that it may take a long time for routers to process it. That would cause the efficiency of the network to fail. Another note we should make here is that if a router gives the wrong information to other routers, all routing decisions will be ineffective.

The next example shows how to find the best routes among all the nodes in a network. The example uses the Shortest Path Dijkstra algorithm. Consider the network shown below:

Let's use the Dijkstra's algorithm to find the routes that A will use to transmit to any of the notes on the network. The Dijkstra's routing algorithm is represented in the following table:

This is how the network looks after all the updates, showing the shortest route among the nodes:

Interior Routing
Packet routing in the Internet is divided into two general groups: interior and exterior routing. Interior routing happens inside or interior to an independent network system. In TCP/IP terminology, these independent network systems are called autonomous systems. Within an autonomous system (AS), routing information is exchanged using an interior routing protocol chosen by the autonomous system's administration. The exterior routing protocols, on the other hand are used between the autonomous systems. Interior routing protocols determine the "best" route to each destination, and they distribute routing information among the systems on a network. There are several interior protocols:

- The Routing Information Protocol (RIP) is the interior protocol most commonly used on UNIX systems. RIP uses distance vector algorithm that selects the route with the lowest "hop count" (metric) as the best route. The RIP hop count represents the number of gateways through which data must pass to reach its destination. RIP assumes that the best route is the one that uses the fewest gateways.

- Hello is a protocol that uses delay as the deciding factor when choosing the best route. Delay is the length of time it takes a datagram to make the round trip between its source and destination.

- Intermediate System to Intermediate System (IS-IS) is an interior routing protocol 	from the OSI protocol suite. It is a link-state protocol. It was the interior routing 	protocol used on the T1 NSFNET backbone. - Open Shortest Path First (OSPF) is another link-state protocol developed for   	TCP/IP. It is suitable for very large networks and provides several advantages 	over RIP.

Routing Information Protocol (RIP)
RIP (Routing Information Protocol) is a standard for exchange of routing information among gateways and hosts. It is a distance-vector protocol. RIP is most useful as an "interior gateway protocol". The network is organized as a collection of "autonomous systems". Each autonomous system has its own routing technology, which may well be different for different autonomous systems. The routing protocol used within an autonomous system is referred to as an interior gateway protocol, or "IGP". Routing Information Protocol (RIP) is designed to work with moderate-size networks using reasonably homogeneous technology. Thus, it is suitable as an Interior Gateway Protocol (IGP) for many campuses and for regional networks using serial lines whose speeds do not vary widely. It is not intended for use in more complex environments. RIP2 derives from RIP, which is an extension of the Routing Information Protocol (RIP) intended to expand the amount of useful information carried in the RIP messages and to add a measure of security. RIP2 is an UDP-based protocol.

What makes RIP work is a routing database that stores information on the fastest route from computer to computer, an update process that enables each router to tell other routers which route is the fastest from its point of view, and an update algorithm that enables each router to update its database with the fastest route communicated from neighboring routers:

Database - Each RIP router on a given network keeps a database that stores the following information for every computer in that network:

IP Address - The Internet Protocol address of the computer.

Gateway - The best gateway to send a message addressed to that IP address.

Distance - The number of routers between this router and the router that can send the message directly to that IP address.

Route change flag - A flag that indicates that this information has changed, used by other routers to update their own databases.

Timers - Various timers.

Algorithm - The RIP algorithm works like this:

Update - At regular intervals each router sends an update message describing its routing database to all the other routers that it is directly connected to. Some routers will send this message as often as every 30 seconds, so that the network will always have up-to-date information to quickly adapt to changes as computers and routers come on and off the network. The Protocol Structure for RIP & and RIP2 is shown in the figure below:

The Protocol Structure for RIP & and RIP2 is shown in the figure below:

Command - The command field is used to specify the purpose of the datagram. There are five commands: Request, Response, Traceon (obsolete), Traceoff (obsolete) and Reserved.

Version - The RIP version number. The current version is 2.

Address family identifier - Indicates what type of address is specified in this particular entry. This is used because RIP2 may carry routing information for several different protocols. The address family identifier for IP is 2.

Route tag - Attribute assigned to a route which must be preserved and readvertised with a route. The route tag provides a method of separating internal RIP routes (routes for networks within the RIP routing domain) from external RIP routes, which may have been imported from an EGP or another IGP.

IP address - The destination IP address.

Subnet mask - Value applied to the IP address to yield the non-host portion of the address. If zero, then no subnet mask has been included for this entry.

Next hop - Immediate next hop IP address to which packets to the destination specified by this route entry should be forwarded.

Metric - Represents the total cost of getting a datagram from the host to that destination. This metric is the sum of the costs associated with the networks that would be traversed in getting to the destination.

Open Shortest Path First Protocol (OSPF)
OSPF is an interior gateway protocol used for between routers that belong to a single Autonomous System. OSPF uses link-state technology in which routers send each other information about the direct connections and links which they have to other routers. Each OSPF router maintains an identical database describing the Autonomous System’s topology. From this database, a routing table is calculated by constructing a shortest- path tree. OSPF recalculates routes quickly in the face of topological changes, utilizing a minimum of routing protocol traffic. An area routing capability is provided, enabling an additional level of routing protection and a reduction in routing protocol traffic. In addition, all OSPF routing protocol exchanges are authenticated. OSPF routes IP packets based solely on the destination IP address found in the IP packet header. IP packets are routed "as is" - they are not encapsulated in any further protocol headers as they transit the Autonomous System. OSPF allows sets of networks to be grouped together. Such a grouping is called an area. The topology of an area is hidden from the rest of the Autonomous System. This information hiding enables a significant reduction in routing traffic. Also, routing within the area is determined only by the area’s own topology, lending the area protection from bad routing data.

The OSPF algorithm works as described below:

Startup - When a router is turned on it sends Hello packets to all of its neighbors, receives their Hello packets in return, and establishes routing connections by synchronizing databases with adjacent routers that agree to synchronize.

Update - At regular intervals each router sends an update message called its "link state" describing its routing database to all the other routers, so that all routers have the same description of the topology of the local network.

Shortest path tree - Each router then calculates a mathematical data structure called a "shortest path tree" that describes the shortest path to each destination address and therefore indicates the closest router to send to for each communication; in other words - "open shortest path first".

The Protocol Structure of OSPF (Open Shortest Path First version 2) is shown below:

Version number - Protocol version number (currently 2).

Packet type - Valid types are as follows: 1 Hello 2 Database Description 3 Link State Request 4 Link State Update 5 Link State Acknowledgment.

Packet length - The length of the protocol packet in bytes. This length includes the standard OSPF header.

Router ID - The router ID of the packet’s source. In OSPF, the source and destination of a routing protocol packet are the two ends of an (potential) adjacency.

Area ID - identifying the area that this packet belongs to. All OSPF packets are associated with a single area. Most travel a single hop only.

Checksum - The standard IP checksum of the entire contents of the packet, starting with the OSPF packet header but excluding the 64-bit authentication field.

AuType - Identifies the authentication scheme to be used for the packet.

Authentication - A 64-bit field for use by the authentication scheme.

Intermediate System to Intermediate System Routing Protocol(IS-IS)
Intermediate System-to-Intermediate System (IS-IS) is a link-state protocol where IS (routers) exchange routing information based on a single metric to determine network topology. It behaves similar to Open Shortest Path First (OSPF) in the TCP/IP network. In an IS-IS network, there are End Systems, Intermediate Systems, Areas and Domains. End systems are user devices. Intermediate systems are routers. Routers are organized into local groups called "areas", and several areas are grouped together into a "domain". IS-IS is designed primarily providing intra-domain routing or routing within an area. IS-IS, working in conjunction with CLNP, ES-IS, and IDRP, provides complete routing over the entire network. IS-IS routing makes use of two-level hierarchical routing. Level 1 - routers know the topology in their area, including all routers and hosts, but they do not know the identity of routers or destinations outside of their area. Level 1 routers forward all traffic for destinations outside of their area to a level 2 router within their area which knows the level 2 topology. Level 2 routers do not need to know the topology within any level 1 area, except to the extent that a level 2 router may also be a level 1 router within a single area. IS-IS has been adapted to carry IP network information, which is called Integrated IS-IS. Integrated IS-IS has the most important characteristic necessary in a modern routing protocol: It supports VLSM and converges rapidly. It is also scalable to support very large networks. There are two types of IS-IS addresses: Network Service Access Point (NSAP) - NSAP addresses identify network layer services, one for each service running. Network Entity Title (NET) - NET addresses identify network layer entities or processes instead of services. Devices may have more than one of each of the two types of addresses. However NET’s should be unique and the System ID portion of the NSAP must be unique for each system. The Protocol Structure of IS-IS (Intermediate System to Intermediate System Routing Protocol) is shown below:

Intra-domain routing protocol discriminator - Network layer protocol identifier assigned to this protocol

Length indicator - Length of the fixed header in octets. Version/protocol ID extension - Equal to 1.

ID length - Length of the ID field of NSAP addresses and NETs used in this routing domain.

R - Reserved bits.

PDU type - Type of PDU. Bits 6, 7 and 8 are reserved.

Version - Equal to 1.

Maximum area addresses - Number of area addresses permitted for this intermediate systems area.

The format of NSAP for IS-IS is shown below:

IDP - Initial Domain Part

AFI - Authority and Format Identifier (1-byte); Provides information about the structure and content of the IDI and DSP fields.

IDI - Initial Domain Identifier (variable length)

DSP - Domain Specific Part

HO-DSP - High Order Domain Specific Part

Area Address (variable)

ID - System ID 1- 8 bytes

SEL - n-selector (1-byte value that serves a function similar to the port number in Internet Protocol).

Exterior Routing
Exterior routing occurs between autonomous systems, and is of concern to service providers and other large or complex networks. The basic routable element is the Autonomous System.While there may be many different interior routing scheme, a single exterior routing system manages the global Internet, based primarily on the BGP-4 exterior routing protocol.

Border Gateway Protocol (BGP)
The Border Gateway Protocol (BGP) ensures that packets get to their destination network regardless of current network conditions. BGP is essentially a distance-vector algorithm, but with several added twists. First, BGP router establishes connections with the other BGP routers with which it directly communicates. The first thing it does is download the entire routing table of each neighboring router. After that it only exchanges much shorter update messages with other routers. BGP routers send and receive update messages to indicate a change in the preferred path to reach a computer with a given IP address. If the router decides to update its own routing tables because this new path is better, then it will subsequently propagate this information to all of the other neighboring BGP routers to which it is connected, and they will in turn decide whether to update their own tables and propagate the information further.

BGP uses the TCP/IP protocol on port 179 to establish connections. It has strong security features, including the incorporation of a digital signature in all communications between BGP routers. Each BGP router contains a Routing Information Base (RIB) that contains the routing information maintained by that router. The RIB contains three types of information:

 * Adj-RIBs-In - The unedited routing information sent by neighboring routers.
 * Loc-RIB - The actual routing information the router uses, developed from Adj-RIBs-In.
 * Adj-RIBs-Out - The information the router chooses to send to neighboring routers.

BGP routers exchange information using four types of messages:

 * Open - Used to open an initial connection with a neighboring router.
 * Update - These messages do most of the work, exchanging routing information between neighboring routers, and contain one of the following pieces of information:
 * Withdrawn routes - The IP addresses of computers that the router no longer can route messages to.
 * Paths - A new preferred route for an IP address. This path consists of two pieces of information - the IP address, and the address of the next router in the path that is used to route messages destined for that address.
 * Notification - Used to indicate errors, such as an incorrect or unreadable message received, and are followed by an immediate close of the connection with the neighboring router.
 * Keepalive - Each BGP router sends a 19 byte Keepalive message to each neighboring router to let them know that it is still operational about every 30 seconds, and no more often than every three seconds. If any router does not receive a Keepalive message from a neighboring router within a set amount of time, it closes its connection with that router, and removes it from its Routing Information Base, repairing what it perceives as damage to the network.

Routing messages are the highest precedence traffic on the Internet, and each BGP router gives them first priority over all other traffic. This makes sense - if routing information can't make it through, then nothing else will.

The BGP algorithm is run after a BGP router receives an update message from a neighboring router, and consists of the following three steps performed for each IP address sent from the neighbor:

 * Update - If the path information for an IP address in the update message is different from the information previously received from that router, then the Adj-RIBs-In database is updated with the newest information.
 * Decision - If it was new information, then a decision process is run that determines which BGP router, of all those presently recorded in the Adj-RIBs-In database, has the best routing path for the IP address in the update message. The algorithm is not mandated, and BGP administrators can set local policy criteria for the decision process such as how long it takes to communicate with each neighboring router, and how long each neighboring router takes to communicate with the next router in the path. If the best path chosen as a result of this decision process is different from the one currently recorded in the Loc-RIB database, then the database is updated.
 * Propagation - If the decision process found a better path, then the Adj-RIBs-Out database is updated as well, and the router sends out update messages to all of its neighboring BGP routers to tell them about the better path. Each neighboring router then runs their own BGP algorithm in turn, decides whether or not to update their routing databases, and then propagates any new and improved paths to neighboring routers in turn.

One of the other important functions performed by the BGP algorithm is to eliminate loops from routing information. For example, a routing loop would occur when router A thinks that router B has the best path to send messages for some computer and B thinks the best path is through C, but C thinks the best path is back through A. If these sort of routing loops were allowed to happen, then any message to that computer that passed through routers A, B, or C would circulate among them forever, failing to deliver the message and using up increasing amounts of network resources. The BGP algorithm traps and stops any such loops.

Hierarchical Routing
In both Link-State and Distance Vector algorithms, every router has to save some information about other routers. When the network size grows, the number of routers in the network increases. As a result, the size of routing tables increases, as well, and routers can not handle network traffic as efficiently. Hierarchical routing are used to overcome this problem. Let us examine an example:

Distance Vector algorithms algorithms are used to find best routes between nodes. In the situation depicted below, every node of the network has to save a routing table with 17 records.

Here is a typical graph and routing table for A:

In hierarchical routing, routers are classified in groups known as regions. Each router has only the information about the routers in its own region and has no information about routers in other regions. That way, routers just save one record in their table for every other region. In this example, we have classified our network into five regions (see below).

If A wants to send packets to any router in region 2 (D, E, F or G), it sends them to B, and so on. As you can see, in this type of routing, the tables can be summarized, so network efficiency improves. The above example shows two-level hierarchical routing. We can also use three-level or four-level hierarchical routing. In three-level hierarchical routing, the network is classified into a number of clusters. Each cluster is made up of a number of regions, and each region contains a number or routers. Hierarchical routing is widely used in Internet routing and makes use of several routing protocols.

Summary
In Distance Vector Algorithms send everything you know to your neighbors, since Link-State Algorithms send info about your neighbors to everyone.

The Message size is small with Link-State Algorithms, and it is potentially large with Distance Vector Algorithms

The message exchange is large in Link-State Algorithms, while in Distance Vector Algorithms, the exchangement is only to neighbors

Convergence speed:

– Link-State Algorithms: fast

– Distance Vector Algorithms: fast with triggered updates

Space requirements:

– Link-State Algorithms maintains entire topology

– Distance Vector Algorithms maintains only neighbor state

Robustness:

• Link-State Algorithms can broadcast incorrect/corrupted LSP – localized problem

• Distance Vector Algorithms can advertise incorrect paths to all destinations – incorrect calculation can spread to entire network

Exercises
1. For the network given below, give global distance-vector tables when

a) each node knows only the distances to its immediate neighbors

b) each node has reported the information it had in the preceding step to its immediate neighbors

c) step b) happens a second time

2. For the network in exercise 1, show how the link-state algorithm builds the routing vector table for node D.

3. For the network given in the figure below, give global distance-vector tables when

a) each node knows only the distances to its immediate neighbors

b) each node has reported the information it had in the preceding step to its immediate neighbors

c) step b) happens a second time

4. Suppose we have the forwarding tables shown below for nodes A and F, in a network where all links have cost 1. Give a diagram of the smallest network consistent with these tables.

For node A we have:

For node F we have:

5. For the network below, find the least cost routes from node A as a source using the Shortest Path Dijkstra's algorithm.

Answers
1. a)

b)

c)

2.

3.

a)

b)

c)

4.

5.

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

title: Communication Networks/Routing