Unicast Routing Protocols

Unicast vs. Multicast

In unicast routing a packet needs to go from a single source to a single destination, while in multicast routing the packet needs to go from a single source to several destinations.

Routing Table

A routing table is a database that contains information about the topology of a network. A router consults a routing table when a datagram is ready for sending. A routing table can be static or dynamic. A static routing table contains information entered manually. The administrator enters the route for each destination into the table. A dynamic routing table is updated periodically by using one of the dynamic routing protocols such as RIP, OSPF, or BGP. Whenever there is a change in the Internet, such as a shutdown of a router or breaking of a link, the dynamic routing protocols update all the tables in the routers (and eventually in the host) automatically.

The following are common fields in a routing table:

• Mask. This field defines the mask applied for the entry.
• Network address. This field defines the network address to which the packet is finally delivered. In the case of host-specific routing, this field defines the address of the destination host.
• Next-hop address. This field defines the address of the next-hop router to which the packet is delivered.
• Interface. This field shows the name of the interface.
• Flags. This field defines up to five flags. Flags are on/off switches that signify either presence or absence. The five flags are U (up), G (gateway), H (host-specific),
• Reference count. This field gives the number of users of this route at the moment. For example, if five people at the same time are connecting to the same host from this router, the value of this column is 5.
• Use. This field shows the number of packets transmitted through this router for the corresponding destination.
• · Metric. This field assigns the cost for passing through network. A single network may have different metrics because different protocols assign metrics differently.

Autonomous System

An internet can be so large that using a single protocol to update all routers in the internet would be very inefficient. Thus the internet is divided into groups of networks and routers called autonomous systems. A single autonomous system is managed by a single administration.

Interior and Exterior Routing

Routing inside an autonomous system is called interior routing. In interior routing, the IP datagram travels from a router to another router of the same network. Routing between autonomous systems is called exterior routing. In exterior routing, an IP datagram travels from a router of one network to the router of another network. Each autonomous system can choose the routing protocol it implements for interior routing. Popular protocols for interior routing are Routing Information Protocol (RIP) and Open Shortest Path First (OSPF). An internet uses only one exterior routing protocol. A popular exterior routing protocol is Border Gateway Protocol (BGP).

The RIP treats all networks as equals. The cost of passing through all routers is one hop count. The OSPF allows the administrator to assign a cost depending on the service required (such as throughput or minimum delay). The BGP assigns metrics based on criterion.

Routing Information Protocol Updating Algorithm

Receive: a response RIP message

1. Add one hop to the hop count for each advertised destination.

2. Repeat the following steps for each advertised destination:

1. If (destination not in the routing table)

1. Add the advertised information to the table.

2. Else If (next-hop field is the same)

1. Replace entry in the table with the advertised one.

2. Else If (advertised hop count smaller than one in the table)

1. Replace entry in the routing table.

3. Return.

Open Shortest Path First (OSPF)

Autonomous System Boundary Routers are responsible for delivering information about other autonomous systems into the current system. Within the autonomous system, the OSPF divides the hosts into areas. Each area has a area border router which summarizes information in the area and distributes it to other areas. All areas are connected to a special area called a backbone and areas can be connected to other areas. The backbone has the AS boundary router. If the direct connection between an area and the backbone the administrator must create a virtual link which may pass though several other areas.

OSPF Connections

• The point-to-point link connects two routers without any other host or router in between.
• The transient link is a network with several routers. Data can come in and out of the network through all the routers. All LANs and some WANs are of this type. To avoid a mesh topology, a router called a designated router is positioned at the center such that every other router has only one neighbor which is the designated router. The designated router is not an additional router. One of the existing routers is “designated” with the task.
• The stub link is a special case of the transient link where the number of routers equals one. All data going in and out of the network pass through this router.
• The virtual link is created when the direct link between two routers has been broken. Because it is not anymore possible for the data to go from router A to router B directly then the data would need to pass fro from router A to router C to router E then finally to router B for example.

Link State Advertisement

Link state advertisements serve to inform the network about the information of an entity’s neighbors. The type of LSA depends on the different entities that broadcast them.

1. Router LSA - the router announces its presence and lists the links to other routers or networks in the same area, together with the metrics to them. Type 1 LSAs are flooded across their own area only.

2. Network LSA - the designated router on a broadcast segment (e.g. Ethernet) lists which routers are joined together by the segment. Type 2 LSAs are flooded across their own area only.

3. Summary LSA to Network - an Area Border Router (ABR) takes information it has learned on one of its attached areas and it can summarize it (but not by default) before sending it out on other areas it is connected to. This summarization helps provide scalability by removing detailed topology information for other areas, because their routing information is summarized into just an address prefix and metric.

4. ASBR-Summary LSA - this is needed because Type 5 External LSAs are flooded to all areas and the detailed next-hop information may not be available in those other areas. This is solved by an Area Border Router flooding the information for the router (i.e. the Autonomous System Boundary Router) where the type 5 originated.

5. External LSA - these LSAs contain information imported into OSPF from other routing processes. They are flooded to all areas (except stub areas).

Topology distribution

When applying link-state algorithms, each node uses as its fundamental data a map of the network in the form of a graph. To produce this, each node floods the entire network with information about what other nodes it can connect to, and each node then independently assembles this information into a map. Using this map, each router then independently determines the least-cost path from itself to every other node using a standard shortest paths algorithm such as Dijkstra's algorithm.

Distance vector algorithms use the Bellman-Ford algorithm. The algorithm operates in a very simple manner. When a node first starts, it only knows of its immediate neighbors, and the direct cost involved in reaching them. (This information, the list of destinations, the total cost to each, and the next hop to send data to get there, makes up the routing table, or distance table.) Each node, on a regular basis, sends to each neighbor its own current idea of the total cost to get to all the destinations it knows of. The neighboring node(s) examine this information, and compare it to what they already 'know'; anything which represents an improvement on what they already have, they insert in their own routing table(s). Over time, all the nodes in the network will discover the best next hop for all destinations, and the best total cost.

Path vector routing is used for exterior routing. Path vector routing became the basis of the Border Gateway Protocol (BGP). It is similar to distance vector routing. In path vector routing we assume there is one node (there can be many) in each autonomous system which acts on behalf of the entire autonomous system. This node is called the speaker node (or autonomous system boundary router). The speaker node creates a routing table (containing the destination, next hop and the path) and advertises it to neighboring speaker nodes in neighboring autonomous systems. The idea is the same as distance vector routing except that only speaker nodes in each autonomous system can communicate with each other.

The Dijkstra algorithm

The Dijkstra (silent j) algorithm is an algorithm which determines the best (shortest) route from a single node to all other nodes. Each route is one source to one destination. The source of the route is only one node but the destination changes though there is only one destination for every shortest route. Thus this is very useful for unicast routing wherein the source node (which is permanent) should know the shortest path to a single destination node (which changes).

Dijkstra algorithm is as follows

1. Start with the local node (router): the root of the tree.

2. Assign a cost of 0 to this node and make it the first permanent node.

3. Examine each neighbor node of the node that was the last permanent node.

4. Assign a cumulative cost to each node and make it tentative.

5. Among the list of tentative nodes

1. Find the node with the smallest cumulative cost and make it permanent.

2. If a node can be reached from more than one direction

1. Select the direction with the shortest cumulative cost.

6. Repeat steps 3 to 5 until every node becomes permanent.

Internet Group Management Protocol

IGMP is a group management protocol. It helps a multicast router create and update a list of loyal members related to each router interface through messages. The types of messages are membership report, leave report and query.

Membership Report - Joining a Group

A host or a router can join a group. A host maintains a list of processes that have member-ship in a group. When a process wants to join a new group, it sends its request to the host. The host adds the name of the process and the name of the requested group to its list. If this is the first entry for this particular group, the host sends a membership report message. If this is not the first entry, there is no need to send the membership report since the host is already a member of the group; it already receives multicast packets for this group.

Leave Report - Leaving a Group

When a host sees that no process is interested in a specific group, it sends a leave report. Similarly, when a router sees that none of the networks connected to its interfaces is interested in a specific group, it sends a leave report about that group.

Query – Monitoring Membership

The router periodically (by default, every 125 s) sends a general query message. In this message, the group address field is set to 0.0.0.0. This means the query for membership continuation is for all groups in which a host is involved, not just one.

Bibliography

Forouzan, B. (2003). Data Communications and Networking 3rd ed. New York: McGraw Hill.

Forouzan, B. (2007). Data Communication and Networking 4th ed. New York: McGraw Hill.

Link-state advertisement. (n.d.). Retrieved October 10, 2010, from Wikipedia: http://en.wikipedia.org/wiki/Link-state_advertisement

Routing. (n.d.). Retrieved October 10, 2010, from Wikipedia: http://en.wikipedia.org/wiki/Routing

The Telephone Network

The telephone network began in the late 1800s which was referred to as plain old telephone system (POTS). It was orignally analog, but with the advancement in computer technology the network started to carry data as well as voice in 1980's. It is now both digital and analog.

Major Components

The telephone network is made of three major components - the local loops, the trunks and the switching office.

The local loop connects the subscriber to the nearest end office (or local central office) through a twisted-pair cable. It has a bandwidth of 4000Hz.

The trunk is a transmission media that connects switching offices. It handles a lot of connections through multiplexing. these are usually optical fibers or satellite links.

The switching office establishes a connection between two subscribers. The connection between two subscribers is not permanent and will only be made upon request. Connections are limited by the total bandwidth of a transmission media therefore having permanent idle lines would limit the services of the network.

LATA

The local telephone network is referred to as Local Access Transport Areas (LATA). LATAs are made up of multiple local loops connected to a tandem office. Services of Comon Carriers (telephone companies) within a LATA are called intra-LATA services. These carriers are refered to as Local Exchange Carriers (LEC). LEC has to types. The Incumbent Local Exchange Carriers (ILEC) is the original company that set up the LATA. To avoid cost for new cabling, Competitive Local Exchange Carriers (CLEC) were allowed to use the LATA of the ILEC for their own services.

Services between LATAs (Inter-LATA services) are handled by Interexchange Carriers (IXC), commonly referred to as long-distance companies. LECs are also allowed to become IXCs. To allow multiple IXCs to use a LATA, a Point of Presence (POP) switching office is created for each IXC.A caller, who needs to connect to a receiver in another LATA, first connects to an end switch then, either directly or through a tandem office, to a POP of the caller's choice. The call then goes from the POP in the caller's LATA to the POP of the same IXC in the reciever's LATA then down to the switching offices and finally to the telephone of the receiver.

Signals

Voice communication used analog signals in the past, but is now moving to digital signals. On the other hand, dialing started with digital signals (rotary) and is now moving to analog signals (touch-tome).

Services

A common carrier may provide Analog and/or Digital services.

Analog Services

Analog Switched Service is the familiar dial-up service most often encountered when a home telehpone is used. Analog Switched services include multiple optional services. Local Call service is normally provided for a flat monthly rate. Toll call services (calls that need to pass through the tandem offices) are charged per call. 800 services are free for the caller and is charged to the callee. 800 services are usually used by companies to encourage customers to call. 900 services are charged to the caller and is normally more expensive than toll call services. This is because the carrier charges two fees - first is charge of the carrier, second the charge of the callee, for example a software company that charges for technical support.

Analog Leased Service offers customers the opportunity to lease a dedicated line that is permanently connected to another customer. Although calls still pass through the switching office, no dialing is needed.

Digital Services

Switched/56 Service is the digital version of the analog switched service. It allows a data rate of up to 56 Kbps. Sender and reciever must both subscribe to this service for connection to happen. Because the line is already digital, the users do not need a modem. All they need to use is a Digital Service Unit (DSU) which changes the rate of the digital data sent by a subscriber to 56Kbps and encodes it in a format used by the carrier.

Digital Data Service is the digital version of an analog leased line with a data rate of up to 64Kbps.

Forouzan, B. (2003). Data Communications and Networking. New York: McGraw Hill.

Wireless Communication and the Electromagnetic Spectrum

The electromagnetic spectrum is the range of all possible frequencies of electromagnetic radiation. As the frequency of an electromagnetic wave increases its wavelength decreases. In any frequency, electromagnetic waves travel through a vacuum at the speed of light. When traveling through a medium the speed of electromagnetic waves decrease.

Data communication frequencies

1. Twisted Pair (0 - 100Mhz)
   
2. Coaxial Cable (1Khz - 1Ghz)
   
3. AM Radio (530Khz - 1600Khz)
   
4. FM Radio (88Mhz - 108hz)
   
5. Terrestrial and Satellite / Microwave (1Ghz - 1Thz)
6. Infrared (1Thz - 100Thz)
   
7. Optical Fiber (100Thz - 1Phz)

Unguided Media

Unguided Media transmit electromagnetic waves without using a solid conductor. Some authors say that air or water is unguided media's media. However it should be noted that Electromagnetic waves do not require any media to propagate and can travel even through vacuum. Wireless Communication would be a better term.


Wireless Data Communication frequencies

1. AM Radio (530Khz - 1600Khz)
   
2. FM Radio (88Mhz - 108hz)
   
3. Terrestrial and Satellite (1Ghz - 100Ghz)
4. Infrared (1Thz - 100Thz)

Propagation Methods

1. Ground Propagation - radio waves travel through the lowest portion of the atmosphere following the curvature of the planet.
2. Sky Propagation - high frequency radio waves radiate upward into the ionosphere where they are reflected back to the earth.
3. Line-of-sight Propagation - very high frequency signals are transmitted in straight lines directly from antenna to antenna.

Wireless Transmission Frequencies

Radio Wave

Although there is no clear cut division between radio waves and microwaves, electromagnetic frequencies between 3Khz and 1Ghz. Behavior of the waves, rather than frequencies, is a better criterion for classification. Radio waves are mostly omnidirectional and propagated using an omnidirectional antenna. When an antenna transmits radio waves, they are propagated in all directions. This means that sending and receiving antennas do not need to be aligned. Radio waves are used for multi-casting, in which there is one sender but many receivers such as AM and RM radio, television, maritime radio, cordless phones and paging. Radio waves can penetrate walls. Radio waves travel to long distances. The disadvantage of omnidirectionality is that the signal is susceptible to interference by another signal of the same frequency. The entire band is regulated by authorities and any part of the band requires permission.

Microwaves

Microwaves have frequencies between 1 and 300 GHz. Microwaves are unidirectional. When an antenna transmits microwaves, they can be narrowly focused. This means that the sending and receiving antennas need to be aligned. This means that even if two pairs of antennas transmit microwaves of the same frequency, they will not interfere with each other as long as the pairs are not aligned. Microwave propagation needs to be line-of-sight. The microwave band is relatively wide. Therefore wider sub-bands can be assigned and a high data rate for each sub-band is possible. Though microwaves travel shorter distances relative to radio waves. Microwaves use unidirectional antennas such as a parabolic dish and a horn antenna. They are used in cellular phones, satellite networks and wireless LANs.

Infrared

Infrared signals, with frequencies from 300Ghz to 4Thz, can be used for short-range communication. Infrared signals, having high frequencies never pass through walls. This is advantageous when communication systems are separated by physical walls. However we can not use infrared outside a building because the sun's rays contain infrared waves that interfere with the communication.

Fiber-optic Cables and the Nature of Light

One of the most significant technological breakthroughs in data transmission has been the creation of the fiber-optic cable. It allows data rate of up to 1600Gbs using WDM. Currently, data rates and bandwidth utilization over fiber-optic cable are limited not by the medium but by the signal generation and reception technology available. The fiber-optic cable transmits electromagnetic signals known as visible light.

A fiber-optic cable has a cylindrical shape and consists of three concentric sections: the core, the cladding and the jacket. The core is made up of dense plastic or glass and it is here that the light travels. The cladding is made up of less dense material which reflects the light signals back to the core instead of absorbing it. The jacket surrounds one or more cladded cores to protect against environmental dangers.

Propagation Modes

Before we discuss propagation modes, we need to discuss how light travels through a medium. Light travels through a straight line as long as it is moving through a single uniform substance. When a light enters another substance it changes direction. If the angle of incidence (the angle the light makes with the line perpendicular to the interface between the two substances) is less than the critical angle, the ray refracts to the substance of lower density. If the angle of incidence is equal to the critical angle, the light bends along the interface. If the angle is greater than the critical angle, the ray reflects and travels again in the denser substance.

Multimode

Multimode fiber-optics transmits multiple light signals. How the beam travel depends on the density composition of the core.

Multimode step-index

The core is evenly dense. The light travels straight until it reaches the interface of the core and cladding. The abrupt change causes it to be reflected back to the core. Step-index refers to the abrupt change of direction of the light. There are multiple paths with varying lengths, therefore varying transmission time which limits the data rate. This is the least expensive propagation mode and its commonly used for local area networks.

Multimode graded-index.

The core is densest at the center and the density decreases gradually towards the edge of the core. This varying density allows the light to bend. This allows focusing the signals more efficiently than step-index. This propagation mode is moderately expensive compared to the other two modes and is commonly used for telephone lines.

Single-mode

Single mode uses step-index fiber and a highly focused light source that limits the light beam to a small range of angles close to the horizontal. The core itself has a small diameter and lower density making the path of the light almost horizontal. The propagation time for all signals are almost equal. Delays are negligible. This is the most expensive propagation mode for fiber-optics commonly used for long distance telecom lines.

Fiber Sizes

Optical fibers are defined by the ration of the diameter of their core to the diameter of their cladding.

Type	Core	Cladding	Mode
50/125	50	125	Multimode, graded-index
62.5/125	62.5	125	Multimode, graded-index
100/125	100	125	Multimode, graded-index
7/125	7	125	Single-mode

Connectors

Subscriber Connectors (SC) is used in cable TV. The Straight-Tip (ST) is used for networking devices. It is more reliable than SC. MT-RJ connector has the same size as the RJ45.

Advantages

1. Very high bandwidth and data rate
2. Less signal attenuation
3. Immunity to electromagnetic interference
4. Resistance to corrosion
5. Light weight
6. Difficult to tap

Disadvantages

1. Installation/maintenance
2. Unidirectional
3. Cost

Coaxial Cable

Like a twisted pair, the coaxial cable consists of two conductors. However, its structure permits a wider range of frequencies. The coaxial cable consists of a hollow outer cylindrical conductor (solid or braided) which surrounds a single conductor (solid or stranded). The outer and inner conductors are separated by insulating strings or a solid dielectric material.

Categories

Coaxial cables are categorized by their radio government ratings (RG). Each RG number denotes a unique set of physical specifications, including the wire gauge of the inner conductor, the thickness and type of the inner insulator, the construction of the shield, and the size and type of the outer casing. Each category is adapted to a particular use.

Category	Impedance	Use
RG-59	75 W	Cable TV
RG-58	50 W	Thin Ethernet
RG-11	50 W	Thick Ethernet

Each type of coaxial cable has a characteristic impedance depending on its dimensions and materials used, which is the ratio of the voltage to the current in the cable. In order to prevent reflections at the destination end of the cable from causing standing waves, any equipment the cable is attached to must present an impedance equal to the characteristic impedance (called 'matching'). Thus the equipment "appears" electrically similar to a continuation of the cable, preventing reflections.

Connectors

The BNC (Bayonet Neill-Concelman) connector is used to connect the cable to a device. The BNC T connector is used to branch out another coaxial cable. The BNC terminator is used at the end of the cable to prevent reflection of the signal.

Advantages

1. Superior bandwidth and data rate compare to twisted pair (350Mhz – 500Mbps)
2. Shielded against crosstalk and external noise without the need for twists

Disadvantages

1. Susceptible to thermal noise and intermodulation noise
2. Rigid and heavy Cable
3. Higher attenuation compared to twisted pairs.

Twisted Pair Cable

The twisted pair consists of two insulated copper wires arranged in a spiral pattern. The pair acts as a single communication link. Normally, a number of these twisted pair cables are wrapped together in a protective sheath. One of the wires is used to carry signals to the receiver and the other is only used to capture the amount of noise. The receiver will then calculate the difference between the two wires. Assuming the wires received the same amount of noise, once the receiver calculates the difference, the receiver would be able to recreate the original signal.

Wire A = original signal + noise

Wire B = noise

original signal = Wire A – Wire B

Twisted pair is normally used in the local loop of the telephone line to provide voice and data channels.

Types

There are two types of twisted pair cables – the Shielded Twisted Pair (STP) and the Unshielded Twisted Pair (UTP). As the name suggests, STP has a metal shield which protects it from noise. This metal shield is absent in the UTP. The STP was created by IBM. Although the shield provides additional protection from noise the cable is bulkier and more expensive. The STP is seldom used outside IBM.

Categories

The Electronic Industries Association (EIA) has developed standards to classify unshielded twisted pair cables into seven categories. Categories are determined by cable quality. Each category is best used with a particular technology.

Category	Bandwidth	Data Rate	Digital/Analog	Use
1	very low	<>	Analog	Telephone
2	<>	2 Mbps	Analog/digital	T-1 lines
3	16 MHz	10 Mbps	Digital	LANs
4	20 MHz	20 Mbps	Digital	LANs
5	100 MHz	100 Mbps	Digital	LANs
6 (draft)	200 MHz	200 Mbps	Digital	LANs
7 (draft)	600 MHz	600 Mbps	Digital	LANs

Why are the wires twisted?

The wires are twisted to reduce noise. Because the wires are twisted, they are affected by noise almost equally. Suppose in one twist one wire is close to the source of noise, in the next twist, the other wire would be closer to the source of noise and so forth. The noise in one wire will cancel out the noise in the other wire. This means that the receiver who calculates the difference between the two receives almost no noise.

Wire A = original signal + noise A

Wire B = noise B

original signal = Wire A – Wire B if an only if noise A = noise B

Connectors

The standard connector for twisted pairs are Registered Jacks (RJ). Some of the common RJs are RJ45 and RJ11.

Advantages

1. Low-cost for local networking
2. Wires are thin and flexible

Disadvantages

1. Limited distance due to strong attenuation
2. The twist loosens over time which makes a difference in the noise received by the wires.
3. Limited bandwidth and data rate (250Khz – 4Mbps)
4. A lot of repeaters or amplifiers are needed for long distance use.