Think you know how routers work? These devices use intricate formulas to figure out exactly where to send a packet and how to get it there.
If you have read the article How Routers Work, then you know that a router is used to manage network traffic and find the best route for sending packets. But have you ever thought about how routers do this? Routers need to have some information about network status in order to make decisions regarding how and where to send packets. But how do they gather this information?
In this article, we'll find out precisely what information is used by routers in determining where to send a packet.
The Basics
Routers use routing algorithms to find the best route to a destination. When we say "best route," we consider parameters like the number of hops (the trip a packet takes from one router or intermediate point to another in the network), time delay and communication cost of packet transmission.
Based on how routers gather information about the structure of a network and their analysis of information to specify the best route, we have two major routing algorithms: global routing algorithms and decentralized routing algorithms. In decentralized routing algorithms, each router has information about the routers it is directly connected to -- it doesn't know about every router in the network. These algorithms are also known as DV (distance vector) algorithms. In global routing algorithms, every router has complete information about all other routers in the network and the traffic status of the network. These algorithms are also known as LS (link state) algorithms. We'll discuss LS algorithms in the next .
LS Algorithms
In LS algorithms, every router has to follow these steps:
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.
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. (Round trip time is a measure of the current delay on a network, found by timing a packet bounced off some remote host.) Note that this 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.
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.
Using an appropriate algorithm, 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.
The Dijkstra algorithm goes through these steps:
The router builds a graph of the network and identifies source and destination nodes, as V1 and V2 for example. Then it builds a matrix, called the "adjacency matrix." In this matrix, a coordinate indicates weight. For example, [i, j] is the weight of a link between Vi and Vj. If there is no direct link between Vi and Vj, this weight is identified as "infinity."
The router builds a status record set for every node on the network. The record contains three fields:
Predecessor field - The first field shows the previous node.
Length field - The second field shows the sum of the weights from the source to that node.
Label field - The last field shows the status of node. Each node can have one status mode: "permanent" or "tentative."
The router initializes the parameters of the status record set (for all nodes) and sets their length to "infinity" and their label to "tentative."
The router sets a T-node. For example, if V1 is to be the source T-node, the router changes V1's label to "permanent." When a label changes to "permanent," it never changes again. A T-node is an agent and nothing more.
The router updates the status record set for all tentative nodes that are directly linked to the source T-node.
The router looks at all of the tentative nodes and chooses the one whose weight to V1 is lowest. That node is then the destination T-node.
If this node is not V2 (the intended destination), the router goes back to step 5.
If this node is V2, the router extracts its previous node from the status record set and does this until it arrives at V1. This list of nodes shows the best route from V1 to V2.
These steps are shown below as a flowchart.
We will use this algorithm as an example on the next .
Example: Dijkstra Algorithm
Here we want to find the best route between A and E (see below). You can see that there are six possible routes between A and E (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.
As you see in the image below, the source node (A) has been chosen as T-node, and so its label is permanent (we show permanent nodes with filled circles and T-nodes with the --> symbol).
In this step, you see that the status record set of tentative nodes directly linked to T-node (B, C) has been changed. Also, since B has less weight, it has been chosen as T-node and its label has changed to permanent (see below).
In this step, like in step 2, the status record set of tentative nodes that have a direct link to T-node (D, E), has been changed. Also, since D has less weight, it has been chosen as T-node and its label has changed to permanent (see below).
In this step, we don't have any tentative nodes, so we just identify the next T-node. Since E has the least weight, it has been chosen as T-node.
E is the destination, so we stop here.
We are at end! Now we have to identify the route. The previous node of E is D, and the previous node of D is B, and B's previous node is A. So the best route is ABDE. In this case, the total weigh is 4 (1+2+1). Although this algorithm works well, it's so complicated that it may take a long time for routers to process it, and the efficiency of the network fails. Also, if a router gives the wrong information to other routers, all routing decisions will be ineffective. To understand this algorithm better, here is the source of program written by C:
#define MAX_NODES 1024 /* maximum number of nodes */
#define INFINITY 1000000000 /* a number larger than every maximum path */
int n,dist[MAX_NODES][MAX_NODES]; /*dist[I][j] is the distance from i to j */
void shortest_path(int s,int t,int path[ ])
{struct state { /* the path being worked on */
int predecessor ; /*previous node */
int length /*length from source to this node*/
enum {permanent, tentative} label /*label state*/
}state[MAX_NODES];
int I, k, min;
struct state *
p;
for (p=&state[0];p < &state[n];p++){ /*initialize state*/
p->predecessor=-1
p->length=INFINITY
p->label=tentative;
}
state[t].length=0; state[t].label=permanent ;
k=t ; /*k is the initial working node */
do{ /* is the better path from k? */
for I=0; I < n; I++) /*this graph has n nodes */
if (dist[k][I] !=0 && state[I].label==tentative){
if (state[k].length+dist[k][I] < state[I].length){
state[I].predecessor=k;
state[I].length=state[k].length + dist[k][I]
}
}
/* Find the tentatively labeled node with the smallest label. */
k=0;min=INFINITY;
for (I=0;I < n;I++)
if(state[I].label==tentative && state[I].length <
min)=state[I].length;
k=I;
}
state[k].label=permanent
}while (k!=s);
/*Copy the path into output array*/
I=0;k=0
Do{path[I++]=k;k=state[k].predecessor;} while (k > =0);
}
DV Algorithms
DV algorithms are also known as Bellman-Ford routing algorithms and Ford-Fulkerson routing algorithms. In these algorithms, every router has a routing table that shows it the best route for any destination. A typical graph and routing table for router J is shown below.
Destination
Weight
Line
A
8
A
B
20
A
C
28
I
D
20
H
E
17
I
F
30
I
G
18
H
H
12
H
I
10
I
J
0
---
K
6
K
L
15
K
A typical network graph and routing table for router J
As the table shows, if router J wants to get packets to router D, it should send them to router H. When packets arrive at router H, it checks its own table and decides how to send the packets to D. In DV algorithms, each router has to follow these steps:
It counts the weight of the links directly connected to it and saves the information to its table.
In a specific period of time, it send its table to its neighbor routers (not to all routers) and receive the routing table of each of its neighbors.
Based on the information in its neighbors' routing tables, it updates its own.
One of the most important problems with DV algorithms is called "count to infinity." Let's examine this problem with an example: Imagine a network with a graph as shown below. As you see in this graph, there is only one link between A and the other parts of the network. Here you can see the graph and routing table of all nodes:
A
B
C
D
A
0,-
1,A
2,B
3,C
B
1,B
0,-
2,C
3,D
C
2,B
1,C
0,-
1,C
D
3,B
2,C
1,D
0,-
Network graph and routing tables
Now imagine that the link between A and B is cut. At this time, B corrects its table. After a specific amount of time, routers exchange their tables, and so B receives C's routing table. Since C doesn't know what has happened to the link between A and B, it says that it has a link to A with the weight of 2 (1 for C to B, and 1 for B to A -- it doesn't know B has no link to A). B receives this table and thinks there is a separate link between C and A, so it corrects its table and changes infinity to 3 (1 for B to C, and 2 for C to A, as C said). Once again, routers exchange their tables. When C receives B's routing table, it sees that B has changed the weight of its link to A from 1 to 3, so C updates its table and changes the weight of the link to A to 4 (1 for C to B, and 3 for B to A, as B said). This process loops until all nodes find out that the weight of link to A is infinity. This situation is shown in the table below. In this way, experts say DV algorithms have a slow convergence rate.
B
C
D
Sum of weight to A after link cut
,A
2,B
3,C
Sum of weight to B after 1st updating
3,C
2,B
3,C
Sum of weight to A after 2nd updating
3,C
4,B
3,C
Sum of weight to A after 3rd updating
5,C
4,B
5,C
Sum of weight to A after 4th updating
5,C
6,B
5,C
Sum of weight to A after 5th updating
7,C
6,B
7,C
Sum of weight to A after nth updating
...
...
...
The "count to infinity" problem
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, C shouldn't send any information to B about A, because B is the only way to A.
Hierarchical Routing
As you see, in both LS and DV algorithms, every router has to save some information about other routers. When the network size grows, the number of routers in the network increases. Consequently, the size of routing tables increases, as well, and routers can't handle network traffic as efficiently. We use hierarchical routing to overcome this problem. Let's examine this subject with an example: We use DV algorithms 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:
Destination
Line
Weight
A
---
---
B
B
1
C
C
1
D
B
2
E
B
3
F
B
3
G
B
4
H
B
5
I
C
5
J
C
6
K
C
5
L
C
4
M
C
4
N
C
3
O
C
4
P
C
2
Q
C
3
Network graph and A's routing table
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. So 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).
Destination
Line
Weight
A
---
---
B
B
1
C
C
1
Region 2
B
2
Region 3
C
2
Region 4
C
3
Region 5
C
4
Hierarchical routing
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- 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.
You hear about fiber-optic cables whenever people talk about the telephone system, the cable TV system or the Internet. Fiber-optic lines are strands of optically pure glass as thin as a human hair that carry digital information over long distances. They are also used in medical imaging and mechanical engineering inspection.
Parts of a single optical fiber
In this article, we will show you how these tiny strands of glass transmit light and the fascinating way that these strands are made.
What are Fiber Optics?
Fiber optics (optical fibers) are long, thin strands of very pure glass about the diameter of a human hair. They are arranged in bundles called optical cables and used to transmit light signals over long distances. If you look closely at a single optical fiber, you will see that it has the following parts:
Core - Thin glass center of the fiber where the light travels
Cladding - Outer optical material surrounding the core that reflects the light back into the core
Buffer coating - Plastic coating that protects the fiber from damage and moisture
Hundreds or thousands of these optical fibers are arranged in bundles in optical cables. The bundles are protected by the cable's outer covering, called a jacket. Optical fibers come in two types:
Single-mode fibers
Multi-mode fibers
Single-mode fibers have small cores (about 3.5 x 10-4 inches or 9 microns in diameter) and transmit infrared laser light (wavelength = 1,300 to 1,550 nanometers). Multi-mode fibers have larger cores (about 2.5 x 10-3 inches or 62.5 microns in diameter) and transmit infrared light (wavelength = 850 to 1,300 nm) from light-emitting diodes (LEDs). Some optical fibers can be made from plastic. These fibers have a large core (0.04 inches or 1 mm diameter) and transmit visible red light (wavelength = 650 nm) from LEDs. Let's look at how an optical fiber works.
How Does an Optical Fiber Transmit Light?
Suppose you want to shine a flashlight beam down a long, straight hallway. Just point the beam straight down the hallway -- light travels in straight lines, so it is no problem. What if the hallway has a bend in it? You could place a mirror at the bend to reflect the light beam around the corner. What if the hallway is very winding with multiple bends? You might line the walls with mirrors and angle the beam so that it bounces from side-to-side all along the hallway. This is exactly what happens in an optical fiber.
Diagram of total internal reflection in an optical fiber
The light in a fiber-optic cable travels through the core (hallway) by constantly bouncing from the cladding (mirror-lined walls), a principle called total internal reflection. Because the cladding does not absorb any light from the core, the light wave can travel great distances. However, some of the light signal degrades within the fiber, mostly due to impurities in the glass. The extent that the signal degrades depends on the purity of the glass and the wavelength of the transmitted light (for example, 850 nm = 60 to 75 percent/km; 1,300 nm = 50 to 60 percent/km; 1,550 nm is greater than 50 percent/km). Some premium optical fibers show much less signal degradation -- less than 10 percent/km at 1,550 nm.
A Fiber-Optic Relay System
To understand how optical fibers are used in communications systems, let's look at an example from a World War II movie or documentary where two naval ships in a fleet need to communicate with each other while maintaining radio silence or on stormy seas. One ship pulls up alongside the other. The captain of one ship sends a message to a sailor on deck. The sailor translates the message into Morse code (dots and dashes) and uses a signal light (floodlight with a venetian blind type shutter on it) to send the message to the other ship. A sailor on the deck of the other ship sees the Morse code message, decodes it into English and sends the message up to the captain. Now, imagine doing this when the ships are on either side of the ocean separated by thousands of miles and you have a fiber-optic communication system in place between the two ships. Fiber-optic relay systems consist of the following:
Transmitter - Produces and encodes the light signals
Optical fiber - Conducts the light signals over a distance
Optical regenerator - May be necessary to boost the light signal (for long distances)
Optical receiver - Receives and decodes the light signals
Transmitter The transmitter is like the sailor on the deck of the sending ship. It receives and directs the optical device to turn the light "on" and "off" in the correct sequence, thereby generating a light signal. The transmitter is physically close to the optical fiber and may even have a lens to focus the light into the fiber. Lasers have more power than LEDs, but vary more with changes in temperature and are more expensive. The most common wavelengths of light signals are 850 nm, 1,300 nm, and 1,550 nm (infrared, non-visible portions of the spectrum). Optical Regenerator As mentioned above, some signal loss occurs when the light is transmitted through the fiber, especially over long distances (more than a half mile, or about 1 km) such as with undersea cables. Therefore, one or more optical regenerators is spliced along the cable to boost the degraded light signals. An optical regenerator consists of optical fibers with a special coating (doping). The doped portion is "pumped" with a laser. When the degraded signal comes into the doped coating, the energy from the laser allows the doped molecules to become lasers themselves. The doped molecules then emit a new, stronger light signal with the same characteristics as the incoming weak light signal. Basically, the regenerator is a laser amplifier for the incoming signal. Optical Receiver The optical receiver is like the sailor on the deck of the receiving ship. It takes the incoming digital light signals, decodes them and sends the electrical signal to the other user's computer, TV or telephone (receiving ship's captain). The receiver uses a photocell or photodiode to detect the light.
Advantages of Fiber Optics
Why are fiber-optic systems revolutionizing telecommunications? Compared to conventional metal wire (copper wire), optical fibers are:
Less expensive - Several miles of optical cable can be made cheaper than equivalent lengths of copper wire. This saves your provider (cable TV, Internet) and you money.
Thinner - Optical fibers can be drawn to smaller diameters than copper wire.
Higher carrying capacity - Because optical fibers are thinner than copper wires, more fibers can be bundled into a given-diameter cable than copper wires. This allows more phone lines to go over the same cable or more channels to come through the cable into your cable TV box.
Less signal degradation - The loss of signal in optical fiber is less than in copper wire.
Light signals - Unlike electrical signals in copper wires, light signals from one fiber do not interfere with those of other fibers in the same cable. This means clearer phone conversations or TV reception.
Low power - Because signals in optical fibers degrade less, lower-power transmitters can be used instead of the high-voltage electrical transmitters needed for copper wires. Again, this saves your provider and you money.
Digital signals - Optical fibers are ideally suited for carrying digital information, which is especially useful in computer networks.
Non-flammable - Because no electricity is passed through optical fibers, there is no fire hazard.
Lightweight - An optical cable weighs less than a comparable copper wire cable. Fiber-optic cables take up less space in the ground.
Flexible - Because fiber optics are so flexible and can transmit and receive light, they are used in many flexible digital cameras for the following purposes:
Medical imaging - in bronchoscopes, endoscopes, laparoscopes
Mechanical imaging - inspecting mechanical welds in pipes and engines (in airplanes, rockets, space shuttles, cars)
Plumbing - to inspect sewer lines
Because of these advantages, you see fiber optics in many industries, most notably telecommunications and computer networks. For example, if you telephone Europe from the United States (or vice versa) and the signal is bounced off a communications satellite, you often hear an echo on the line. But with transatlantic fiber-optic cables, you have a direct connection with no echoes.
How Are Optical Fibers Made?
Now that we know how fiber-optic systems work and why they are useful -- how do they make them? Optical fibers are made of extremely pure optical glass. We think of a glass window as transparent, but the thicker the glass gets, the less transparent it becomes due to impurities in the glass. However, the glass in an optical fiber has far fewer impurities than window-pane glass. One company's description of the quality of glass is as follows: If you were on top of an ocean that is miles of solid core optical fiber glass, you could see the bottom clearly. Making optical fibers requires the following steps:
Making a preform glass cylinder
Drawing the fibers from the preform
Testing the fibers
Making the Preform Blank The glass for the preform is made by a process called modified chemical vapor deposition (MCVD).
MCVD process for making the preform blank
In MCVD, oxygen is bubbled through solutions of silicon chloride (SiCl4), germanium chloride (GeCl4) and/or other chemicals. The precise mixture governs the various physical and optical properties (index of refraction, coefficient of expansion, melting point, etc.). The gas vapors are then conducted to the inside of a synthetic silica or quartz tube (cladding) in a special lathe. As the lathe turns, a torch is moved up and down the outside of the tube. The extreme heat from the torch causes two things to happen:
Lathe used in preparing the preform blank
The silicon and germanium react with oxygen, forming silicon dioxide (SiO2) and germanium dioxide (GeO2).
The silicon dioxide and germanium dioxide deposit on the inside of the tube and fuse together to form glass.
The lathe turns continuously to make an even coating and consistent blank. The purity of the glass is maintained by using corrosion-resistant plastic in the gas delivery system (valve blocks, pipes, seals) and by precisely controlling the flow and composition of the mixture. The process of making the preform blank is highly automated and takes several hours. After the preform blank cools, it is tested for quality control (index of refraction). Drawing Fibers from the Preform Blank Once the preform blank has been tested, it gets loaded into a fiber drawing tower.
Diagram of a fiber drawing tower used to draw optical glass fibers from a preform blank
The blank gets lowered into a graphite furnace (3,452 to 3,992 degrees Fahrenheit or 1,900 to 2,200 degrees Celsius) and the tip gets melted until a molten glob falls down by gravity. As it drops, it cools and forms a thread.
The operator threads the strand through a series of coating cups (buffer coatings) and ultraviolet light curing ovens onto a tractor-controlled spool. The tractor mechanism slowly pulls the fiber from the heated preform blank and is precisely controlled by using a laser micrometer to measure the diameter of the fiber and feed the information back to the tractor mechanism. Fibers are pulled from the blank at a rate of 33 to 66 ft/s (10 to 20 m/s) and the finished product is wound onto the spool. It is not uncommon for spools to contain more than 1.4 miles (2.2 km) of optical fiber. Testing the Finished Optical Fiber The finished optical fiber is tested for the following:
Tensile strength - Must withstand 100,000 lb/in2 or more
Refractive index profile - Determine numerical aperture as well as screen for optical defects
Photo courtesy Corning Finished spool of optical fiber
Fiber geometry - Core diameter, cladding dimensions and coating diameter are uniform
Attenuation - Determine the extent that light signals of various wavelengths degrade over distance
Information carrying capacity (bandwidth) - Number of signals that can be carried at one time (multi-mode fibers)
Chromatic dispersion - Spread of various wavelengths of light through the core (important for bandwidth)
Operating temperature/humidity range
Temperature dependence of attenuation
Ability to conduct light underwater - Important for undersea cables
Once the fibers have passed the quality control, they are sold to telephone companies, cable companies and network providers. Many companies are currently replacing their old copper-wire-based systems with new fiber-optic-based systems to improve speed, capacity and clarity.
Physics of Total Internal Reflection
When light passes from a medium with one index of refraction (m1) to another medium with a lower index of refraction (m2), it bends or refracts away from an imaginary line perpendicular to the surface (normal line). As the angle of the beam through m1 becomes greater with respect to the normal line, the refracted light through m2 bends further away from the line. At one particular angle (critical angle), the refracted light will not go into m2, but instead will travel along the surface between the two media (sine [critical angle] = n2/n1 where n1 and n2 are the indices of refraction [n1 is greater than n2]). If the beam through m1 is greater than the critical angle, then the refracted beam will be reflected entirely back into m1 (total internal reflection), even though m2 may be transparent! In physics, the critical angle is described with respect to the normal line. In fiber optics, the critical angle is described with respect to the parallel axis running down the middle of the fiber. Therefore, the fiber-optic critical angle = (90 degrees - physics critical angle).
Total internal reflection in an optical fiber
In an optical fiber, the light travels through the core (m1, high index of refraction) by constantly reflecting from the cladding (m2, lower index of refraction) because the angle of the light is always greater than the critical angle. Light reflects from the cladding no matter what angle the fiber itself gets bent at, even if it's a full circle! Because the cladding does not absorb any light from the core, the light wave can travel great distances. However, some of the light signal degrades within the fiber, mostly due to impurities in the glass. The extent that the signal degrades depends upon the purity of the glass and the wavelength of the transmitted light (for example, 850 nm = 60 to 75 percent/km; 1,300 nm = 50 to 60 percent/km; 1,550 nm is greater than 50 percent/km). Some premium optical fibers show much less signal degradation -- less than 10 percent/km at 1,550 nm.
The Internet is one of the 20th century's greatest communications developments. It allows people around the world to send e-mail to one another in a matter of seconds.
We're all used to seeing the various parts of the Internet that come into our homes and offices -- the Web pages, e-mail messages and downloaded files that make the Internet a dynamic and valuable medium. But none of these parts would ever make it to your computer without a piece of the Internet that you've probably never seen. In fact, most people have never stood "face to machine" with the technology most responsible for allowing the Internet to exist at all: the router.
Keeping the Messages Moving
When you send e-mail to a friend on the other side of the country, how does the message know to end up on your friend's computer, rather than on one of the millions of other computers in the world? Much of the work to get a message from one computer to another is done by routers, because they're the crucial devices that let messages flow between networks, rather than within networks.
Let's look at what a very simple router might do. Imagine a small company that makes animated 3-D graphics for local television stations. There are 10 employees of the company, each with a computer. Four of the employees are animators, while the rest are in sales, accounting and management. The animators will need to send lots of very large files back and forth to one another as they work on projects. To do this, they'll use a network. When one animator sends a file to another, the very large file will use up most of the network's capacity, making the network run very slowly for other users. One of the reasons that a single intensive user can affect the entire network stems from the way that Ethernet works. Each information packet sent from a computer is seen by all the other computers on the local network. Each computer then examines the packet and decides whether it was meant for its address. This keeps the basic plan of the network simple, but has performance consequences as the size of the network or level of network activity increases. To keep the animators' work from interfering with that of the folks in the front office, the company sets up two separate networks, one for the animators and one for the rest of the company. A router links the two networks and connects both networks to the Internet.
Directing Traffic
The router is the only device that sees every message sent by any computer on either of the company's networks. When the animator in our example sends a huge file to another animator, the router looks at the recipient's address and keeps the traffic on the animator's network. When an animator, on the other hand, sends a message to the bookkeeper asking about an expense-account check, then the router sees the recipient's address and forwards the message between the two networks. One of the tools a router uses to decide where a packet should go is a configuration table. A configuration table is a collection of information, including:
Information on which connections lead to particular groups of addresses
Priorities for connections to be used
Rules for handling both routine and special cases of traffic
A configuration table can be as simple as a half-dozen lines in the smallest routers, but can grow to massive size and complexity in the very large routers that handle the bulk of Internet messages. A router, then, has two separate but related jobs:
The router ensures that information doesn't go where it's not needed. This is crucial for keeping large volumes of data from clogging the connections of "innocent bystanders."
The router makes sure that information does make it to the intended destination.
In performing these two jobs, a router is extremely useful in dealing with two separate computer networks. It joins the two networks, passing information from one to the other and, in some cases, performing translations of various protocols between the two networks. It also protects the networks from one another, preventing the traffic on one from unnecessarily spilling over to the other. As the number of networks attached to one another grows, the configuration table for handling traffic among them grows, and the processing power of the router is increased. Regardless of how many networks are attached, though, the basic operation and function of the router remains the same. Since the Internet is one huge network made up of tens of thousands of smaller networks, its use of routers is an absolute necessity.
Transmitting Packets
When you make a telephone call to someone on the other side of the country, the telephone system establishes a stable circuit between your telephone and the telephone you're calling. The circuit might involve a half dozen or more steps through copper cables, switches, fiber optics, microwaves and satellites, but those steps are established and remain constant for the duration of the call. This circuit approach means that the quality of the line between you and the person you're calling is consistent throughout the call, but a problem with any portion of the circuit -- maybe a tree falls across one of the lines used, or there's a power problem with a switch -- brings your call to an early and abrupt end. When you send an e-mail message with an attachment to the other side of the country, a very different process is used.
Internet data, whether in the form of a Web page, a downloaded file or an e-mail message, travels over a system known as a packet-switching network. In this system, the data in a message or file is broken up into packages about 1,500 bytes long. Each of these packages gets a wrapper that includes information on the sender's address, the receiver's address, the package's place in the entire message, and how the receiving computer can be sure that the package arrived intact. Each data package, called a packet, is then sent off to its destination via the best available route -- a route that might be taken by all the other packets in the message or by none of the other packets in the message. This might seem very complicated compared to the circuit approach used by the telephone system, but in a network designed for data there are two huge advantages to the packet-switching plan.
The network can balance the load across various pieces of equipment on a millisecond-by-millisecond basis.
If there is a problem with one piece of equipment in the network while a message is being transferred, packets can be routed around the problem, ensuring the delivery of the entire message.
The Path of a Packet
The routers that make up the main part of the Internet can reconfigure the paths that packets take because they look at the information surrounding the data packet, and they tell each other about line conditions, such as delays in receiving and sending data and traffic on various pieces of the network. Not all routers do so many jobs, however. Routers come in different sizes. For example:
If you have enabled Internet connection sharing between two Windows 98-based computers, you're using one of the computers (the computer with the Internet connection) as a simple router. In this instance, the router does so little -- simply looking at data to see whether it's intended for one computer or the other -- that it can operate in the background of the system without significantly affecting the other programs you might be running.
Slightly larger routers, the sort used to connect a small office network to the Internet, will do a bit more. These routers frequently enforce rules concerning security for the office network (trying to secure the network from certain attacks). They handle enough traffic that they're generally stand-alone devices rather than software running on a server.
The largest routers, those used to handle data at the major traffic points on the Internet, handle millions of data packets every second and work to configure the network most efficiently. These routers are large stand-alone systems that have far more in common with super computers than with your office server.
Routing Packets: An Example
Let's take a look at a medium-sized router -- the router we use in the office. In our case, the router only has two networks to worry about: The office network, with about 50 computers and devices, and the Internet. The office network connects to the router through an Ethernet connection, specifically a 100 base-T connection (100 base-T means that the connection is 100 megabits per second, and uses a twisted-pair cable like an 8-wire version of the cable that connects your telephone to the wall jack). There are two connections between the router and our ISP (Internet service provider). One is a T-1 connection that supports 1.5 megabits per second. The other is an ISDN line that supports 128 kilobits per second. The configuration table in the router tells it that all out-bound packets are to use the T-1 line, unless it's unavailable for some reason (perhaps a backhole digs up the cable). If it can't be used, then outbound traffic goes on the ISDN line. This way, the ISDN line is held as "insurance" against a problem with the faster T-1 connection, and no action by a staff member is required to make the switch in case of trouble. The router's configuration table knows what to do. In addition to routing packets from one point to another, the router has rules limiting how computers from outside the network can connect to computers inside the network, how the network appears to the outside world, and other security functions. While most companies also have a special piece of hardware or software called a firewall to enforce security, the rules in a router's configuration table are important to keeping a company's (or family's) network secure. One of the crucial tasks for any router is knowing when a packet of information stays on its local network. For this, it uses a mechanism called a subnet mask. The subnet mask looks like an IP address and usually reads "255.255.255.0." This tells the router that all messages with the sender and receiver having an address sharing the first three groups of numbers are on the same network, and shouldn't be sent out to another network. Here's an example: The computer at address 15.57.31.40 sends a request to the computer at 15.57.31.52. The router, which sees all the packets, matches the first three groups in the address of both sender and receiver (15.57.31), and keeps the packet on the local network. (You'll learn more about how the addresses work in the next section.) Between the time these words left the server and the time they showed up on your monitor, they passed through several routers (it's impossible to know ahead of time exactly how many "several" might be) that helped them along the way. It's very similar to the process that gets a postal letter from your mailbox to the mailbox of a friend, with routers taking the place of the mail sorters and handlers along the way.
Knowing Where to Send Data
Routers are one of several types of devices that make up the "plumbing" of a computer network. Hubs, switches and routers all take signals from computers or networks and pass them along to other computers and networks, but a router is the only one of these devices that examines each bundle of data as it passes and makes a decision about exactly where it should go. To make these decisions, routers must first know about two kinds of information: addresses and network structure. When a friend mails a birthday card to be delivered to you at your house, he probably uses an address that looks something like this:
Joe Smith 123 Maple Street Smalltown, FL 45678
The address has several pieces, each of which helps the people in the postal service move the letter along to your house. The ZIP code can speed the process up; but even without the ZIP code, the card will get to your house as long as your friend includes your state, city and street address. You can think of this address as a logical address because it describes a way someone can get a message to you. This logical address is connected to a physical address that you generally only see when you're buying or selling a piece of property. The survey plot of the land and house, with latitude, longitude or section bearings, gives the legal description, or address, of the property.
Logical Addresses
Every piece of equipment that connects to a network, whether an office network or the Internet, has a physical address. This is an address that's unique to the piece of equipment that's actually attached to the network cable. For example, if your desktop computer has a network interface card (NIC) in it, the NIC has a physical address permanently stored in a special memory location. This physical address, which is also called the MAC address (for Media Access Control) has two parts, each 3 bytes long. The first 3 bytes identify the company that made the NIC. The second 3 bytes are the serial number of the NIC itself. The interesting thing is that your computer can have several logical addresses at the same time. Of course, you're used to having several "logical addresses" bring messages to one physical address. Your mailing address, telephone number (or numbers) and home e-mail address all work to bring messages to you when you're in your house. They are simply used for different types of messages -- different networks, so to speak. Logical addresses for computer networks work in exactly the same way. You may be using the addressing schemes, or protocols, from several different types of networks simultaneously. If you're connected to the Internet (and if you're reading this, you probably are), then you have an address that's part of the TCP/IP network protocol. If you also have a small network set up to exchange files between several family computers, then you may also be using the Microsoft NetBEUI protocol. If you connect to your company's network from home, then your computer may have an address that follows Novell's IPX/SPX protocol. All of these can coexist on your computer. Since the driver software that allows your computer to communicate with each network uses resources like memory and CPU time, you don't want to load protocols you won't need, but there's no problem with having all the protocols your work requires running at the same time. On the next , you’ll learn how to find your computer’s MAC address.
MAC Addresses
The chances are very good that you'll never see the MAC address for any of your equipment because the software that helps your computer communicate with a network takes care of matching the MAC address to a logical address. The logical address is what the network uses to pass information along to your computer. If you'd like to see the MAC address and logical address used by the Internet Protocol (IP) for your Windows computer, you can run a small program that Microsoft provides. Go to the "Start" menu, click on "Run," and in the window that appears, type WINIPCFG (IPCONFIG/ALL for Windows 2000/XP). When the gray window appears, click on "More Info" and you'll get this sort of information: Windows 98 IP Configuration: Host Name: NAMESITEWORKS DNS Servers: 208.153.64.20  208.153.0.5 Node Type: Broadcast NetBIOS Scope ID: IP Routing Enabled: Yes WINS Proxy Enabled: No NetBIOS Resolution Uses DNS: No
There's a lot of information here that will vary depending on exactly how your connection to the Internet is established, but the physical address is the MAC address of the adapter queried by the program. The IP address is the logical address assigned to your connection by your ISP or network administrator. You'll see the addresses of other servers, including the DNS servers that keep track of all the names of Internet sites and the gateway server that you connect to in order to reach the Internet. When you've finished looking at the information, click OK. (Note: For security reasons, some of the information about this connection to the Internet has been changed. You should be very careful about giving your computer's information to other people -- with your address and the right tools, an unscrupulous person could, in some circumstances, gain access to your personal information and control your system through a " Trojan Horse" program.
Understanding the Protocols
The first and most basic job of the router is to know where to send information addressed to your computer. Just as the mail handler on the other side of the country knows enough to keep a birthday card coming toward you without knowing where your house is, most of the routers that forward an e-mail message to you don't know your computer's MAC address, but they know enough to keep the message flowing. Routers are programmed to understand the most common network protocols. That means they know the format of the addresses, how many bytes are in the basic package of data sent out over the network, and how to make sure all the packages reach their destination and get reassembled. For the routers that are part of the Internet's main "backbone," this means looking at, and moving on, millions of information packages every second. And simply moving the package along to its destination isn't all that a router will do. It's just as important, in today's computerized world, that they keep the message flowing by the best possible route. In a modern network, every e-mail message is broken up into small pieces. The pieces are sent individually and reassembled when they're received at their final destination. Because the individual pieces of information are called packets and each packet can be sent along a different path, like a train going through a set of switches, this kind of network is called a packet-switched network. It means that you don't have to build a dedicated network between you and your friend on the other side of the country. Your e-mail flows over any one of thousands of different routes to get from one computer to the other. Depending on the time of day and day of the week, some parts of the huge public packet-switched network may be busier than others. When this happens, the routers that make up this system will communicate with one another so that traffic not bound for the crowded area can be sent by less congested network routes. This lets the network function at full capacity without excessively burdening already-busy areas. You can see, though, how Denial of Service attacks (described in the next section), in which people send millions and millions of messages to a particular server, will affect that server and the routers forwarding message to it. As the messages pile up and pieces of the network become congested, more and more routers send out the message that they're busy, and the entire network with all its users can be affected.
Tracing a Message
If you're using a Microsoft Windows-based system, you can see just how many routers are involved in your Internet traffic by using a program you have on your computer. The program is called Traceroute, and that describes what it does -- it traces the route that a packet of information takes to get from your computer to another computer connected to the Internet. To run this program, click on the "MS-DOS Prompt" icon on the "Start" menu. Then, at the "C:\WINDOWS>" prompt, type "tracert www.site name.com". When I did this from my office in Florida, the results looked like this:
The first number shows how many routers are between your computer and the router shown. In this instance, there were a total of 14 routers involved in the process (number 15 is the Web server). The next three numbers show how long it takes a packet of information to move from your computer to the router shown and back again. Next, in this example, starting with step six, comes the "name" of the router or server. This is something that helps people looking at the list but is of no importance to the routers and computers as they move traffic along the Internet. Finally, you see theInternal Protocol (IP) address of each computer or router. The final picture of this trace route shows that there were 14 routers between the Web server and me and that it took, on average, a little more than 2.5 seconds for information to get from my computer to the server and back again. You can use Traceroute to see how many routers are between you and any other computer you can name or know the IP address for. It can be interesting to see how many steps are required to get to computers outside your nation. Since I live in the United States, I decided to see how many routers were between my computer and the Web server for the British Broadcasting Corporation. At the C:\WINDOWS> prompt, I typed tracert www.bbc.com. The result was this:
You can see that it took only one more step to reach a Web server on the other side of the Atlantic Ocean than it did to reach a server two states away! On the next , we'll go into detail about Denial of Service attacks.
Denial of Service Attacks
In the first quarter of 2000, there were several attacks on very popular Web sites. Most of these were "Denial of Service" attacks -- attacks that served to prevent regular readers and customers of the sites from getting a response to their requests. How did someone manage to do this? They did it by flooding the servers, and their attached routers, with requests for information at a rate far too great for the system to handle. Most routers have rules in the configuration table that won't allow millions of requests from the same sending address. If too many requests from one address are received in a short period of time, the router simply discards them without forwarding. The people responsible for the attacks knew this, so they illicitly planted programs on many different computers. These programs, when triggered, began sending thousands of requests a minute to one or more Web sites. The programs "spoofed" the IP address of the sender, placing a different false IP address on each packet so that the routers' security rules wouldn't be triggered. When the packet floods were triggered, millions of requests for information began to hit the targeted Web sites. While the servers were being heavily taxed by the requests, the real impact was to the routers just "upstream" from the servers. Suddenly these routers, which were robust but of a size appropriate for normal traffic, were getting the levels of requests normally associated with Internet backbone routers. They couldn't handle the massive number of packets, and began discarding packets and sending status messages to other routers stating that the connection was full. As these messages cascaded through the routers leading to attacked servers, all paths to the servers were clogged, legitimate traffic couldn't get through the logjam, and the attackers' goals were accomplished. Web content providers and router companies have placed new rules designed to prevent such an attack in the configuration tables, and the companies and universities whose computers were used to launch the attacks have worked to prevent their systems being used maliciously. Whether their defenses, or the new attacks designed by criminals, will prevail remains to be seen.
Backbone of the Internet
In order to handle all the users of even a large private network, millions and millions of traffic packets must be sent at the same time. Some of the largest routers are made by Cisco Systems, Inc, a company that specializes in networking hardware. Cisco's Gigabit Switch Router 12000 series of routers is the sort of equipment that is used on the backbone of the Internet. These routers use the same sort of design as some of the most powerful supercomputers in the world, a design that ties many different processors together with a series of extremely fast switches. The 12000 series uses 200-MHz MIPS R5000 processors, the same type of processor used in the workstations that generate much of the computer animation and special effects used in movies. The largest model in the 12000 series, the 12016, uses a series of switches that can handle up to 320 billion bits of information per second and, when fully loaded with boards, move as many as 60 million packets of data every second. Beyond the computing power of the processors, these routers can handle so much information because they are very highly specialized. Relieved of the burden of displaying 3-D graphics and waiting for mouse input, modern processors and software can cope with amazing amounts of information.
Even with the computing power available in a very large router, how does it know which of the many possibilities for outbound connection a particular packet should take? The answer lies back in the configuration table. The router will scan the destination address and match that IP address against rules in the configuration table. The rules will say that packets in a particular group of addresses (a group that may be large or small, depending on precisely where the router is) should go in a specific direction. Next the router will check the performance of the primary connection in that direction against another set of rules. If the performance of the connection is good enough, the packet is sent, and the next packet handled. If the connection is not performing up to expected parameters, then an alternate is chosen and checked. Finally, a connection will be found with the best performance at a given moment, and the packet will be sent on its way. All of this happens in a tiny fraction of a second, and this activity goes on millions of times a second, around the world, 24 hours every day. Knowing where and how to send a message is the most important job of a router. Some simple routers do this and nothing more. Other routers add additional functions to the jobs they perform. Rules about where messages from inside a company may be sent and from which companies messages are accepted can be applied to some routers. Others may have rules that help minimize the damage from "denial of service" attacks. The one constant is that modern networks, including the Internet, could not exist without the router.
Just as Atari ushered in the dawn of the home video game, Nintendo is largely considered to be the company that revolutionized the industry with the introduction of the Nintendo Entertainment System (NES) in 1985. An 8-bit system based on the 6502 processor and some custom chips, the NES came together with Super Mario Brothers; this inclusion of an accurate home version of one of the most popular arcade games at the time turned out to be pure genius. Sales of the NES were phenomenal. This established Nintendo as the dominant home video game manufacturer until the late '90s, when it was eclipsed by the rival Sony PlayStation.
Competition from 32-bit systems prompted Nintendo to develop the 64-bit system that became known as Nintendo 64.
In 1989, Nintendo introduced a new 16-bit system dubbed the Super Nintendo Entertainment System (SNES). Within a couple of years, rivals had introduced 32-bit systems that eclipsed the capabilities of the SNES. So, Nintendo announced an agreement with Silicon Graphics Inc. (SGI) to develop a new 64-bit video game system, code-named Project Reality. Although SGI had never designed video game hardware before, the company was regarded as one of the leaders in computer graphics technology.
After several years of development, the system was finally released in 1996 as the Nintendo 64. But the delays and shortage of games during the first year of availability gave the advantage to Sony, who had released the PlayStation over a year earlier. Nintendo is facing the same situation again with the Sony PlayStation 2 debuting in 2000, while Nintendo's Gamecube is not due until Fall 2001.
Console
Let's take a look at the components inside an N64, and what their capabilities are.
Processor: 64-bit R4300i "Reality Engine"
Processor clock speed: 93.75 MHz
Bus speed: 562.5 MB per second
Co-Processor: "Reality Co-Processor," 62.5 MHz custom chip that combines two systems:
Graphics: "Reality Immersion Processor"
Processor clock speed: 62.5 MHz
MIPS (Million Instructions Per Second): 500
Resolution: 640x480, 320x240 or 256x224 interlaced
Colors: 21-bit (2,097,152) maximum
Polygon rendering: 150,000 polygons per second
Geometry engine:
Anti-aliasing
Perspective correction
Gouraud shading
Trilinear mip mapping
Environment mapping
Memory: uses system memory
Audio: "Reality Signal Processor"
Channels: 64
Sample rate: 44.1 KHz
Memory: uses system memory
Memory: 4 MB Rambus D-RAM (expands to 8 MB)
Operating system: Proprietary
Game medium: Cartridge
Similar to the PlayStation, the CPU in the N64 is a RISC processor. RISC stands for reduced instruction set computer, and means that the instructions and computations performed by the processor are simpler and fewer. Also, RISC chips are superscalar -- they can perform multiple instructions at the same time. This combination of capabilities, performing multiple instructions simultaneously and completing each instruction faster because it is simpler, allows the CPU to perform better than many chips with a much faster clock speed.
Nintendo 64 uses a customized chip that handles all the components.
To lower production costs, the CPU, graphics and audio processors are combined into a single application specific integrated circuit, or ASIC. Simply put, the ASIC is a customized chip created to manage all of the components that would otherwise be handled by three separate chips.
Some special features of the N64 include perspective correction and trilinear mip mapping. Perspective correction makes the texture map resize at the same rate as the object that it is mapped on.
Trilinear mip mapping is a cool process. In this form of texture mapping, three sizes of each texture map are made, a large, a medium and a small version. In essence, it replaces the appearance of an object with a more detailed image as you move closer to the object in the game. Let's take a look at how it uses these maps:
The system calculates the distance from your viewpoint to an object in the game.
The system loads the texture maps for the object. Our three maps will be 64x64 (large), 32x32 (medium), and 8x8 (small).
The system determines the exact size that the image map needs to be -- let's say 16x16 for our example here.
Based on the size, it decides which two texture maps to use. For our example, it might choose the medium and small texture maps.
It then interpolates (averages) between the two texture maps, creating a custom texture map that is 16x16, which it then applies to the object.
Environment mapping is no less amazing. Simple in concept, it means that reflections of objects are rendered and mapped onto the reflecting surface. The sheer amount of calculating that is done by the graphics processor to determine the angle and transparency for each reflected object, and then render it in real time, is extraordinary. An incredible number of calculations have to happen for every single polygon in a game. And there can be over a hundred thousand polygons on the screen at any given time!
The games come on proprietary ROMs housed in plastic cartridges. When a game is put in the console, the following happens:
You turn the power on.
The console loads portions of the operating system from ROM into RAM.
The game initialization sequence is loaded into RAM.
You interact with the game via the controller.
As each specific part of the game is requested, the application code, video, audio and hardware-render geometry are loaded into RAM.
The CPU coordinates everything. It receives the input from the controller, pulls the data from RAM and directs the graphics and audio processing.
You are finally beaten by the game and turn it off.
Controller
The trident shape of the Nintendo 64 controller is unique among video game systems.
The controller is the primary user interface for the N64. With its trident shape, it is probably the most unusual design for a controller on the market today. The standard N64 controller has 14 buttons plus an analog joystick. The buttons include:
Four buttons arranged as a directional pad on the top left
Start button in the top middle
Six action buttons on the top right
One action button on the front left
One action button on the front right
One action button in the bottom middle
Analog joystick on the top middle
Inside the N64 controller.
Although each button can be configured to perform a specific and distinctive action, they all work on the same principle. In essence, each button is a switch that completes a circuit when it is pressed. A small metal disk beneath the button is pushed into contact with two strips of conductive material on the circuit board inside the controller. While the metal disk is in contact, it conducts electricity between the two strips. The controller senses that the circuit is closed and sends that data to the N64. The CPU compares that data with the instructions in the game software for that button, and triggers the appropriate response. There is also a metal disk under each arm of the directional pad. If you're playing a game in which pushing down on the directional pad causes the character to crouch, a similar string of connections is made from the time you push down on the pad to when the character crouches.
The analog joystick works in a completely different way from the buttons described above. Two wheels are positioned at right angles to each other below the joystick. Whenever the joystick is moved, the two wheels turn slightly. Tiny slots are arranged around the perimeter of each wheel. The wheels are each mounted between an LED (Light Emitting Diode) and a photo cell. Light from the LED, shining through the slots in the wheel on the cell, creates a small amount of current. When the amount of light changes, the level of current changes. By monitoring the output of each photo cell, the N64 can determine the exact angle at which the joystick is being held, and trigger the appropriate response.
Another feature of the N64 controller is the ability to add options via an expansion slot on the bottom of the controller. A popular option is the Rumble Pak, which provides force feedback. This feature provides a tactile stimulation to certain actions in a game. For example, in a racing game, you might feel a jarring vibration as your car slams into the wall.
Force feedback is actually accomplished through the use of a very common device, a simple electric motor. The shaft of the motor holds an unbalanced weight. When power is supplied to the motor, it spins the weight. Because the weight is unbalanced, the motor tries to wobble. But since the motor is securely mounted inside the Rumble Pak, the wobble translates into a shuddering vibration of the controller itself.
You can save games and high scores by using one of the special Flash memory cards. The card is inserted into the slot on the bottom of the N64 controller.
The N64 controller uses only three wires to connect to the console. There's a ground wire, another wire that supplies +3, 6 volts of power, and a third wire that carries all data. The controller sends the information for each button in sequence, and then receives data back from the console.
Games
Cartridges are unique to Nintendo 64. They offer fast load but small capacity. They are more durable than CDs.
The N64 is the only current system that uses cartridges. There are advantages and disadvantages to this approach:
Advantages
Fast load times - Sections of a game are transferred almost instantly from the cartridge's ROM to the system's RAM.
Additional performance features - Since the cartridge contains a circuit board that is plugged into the main system, it can contain special hardware-based enhancements that augment the processing power or special effects of the system.
Durability - Cartridges are not as easily damaged as CDs, which can be ruined by a simple scratch.
Disadvantages
Small capacity - Cartridges, ranging from about 8 MB to 96 MB, hold significantly less data than CDs (650 MB).
Expense - Because of all the hardware, the cost per unit to manufacture cartridges is quite a bit more than to make CDs.
Audio - Even though the N64 has near-CD quality sound, it is not utilized to the same degree as in CD-based games because of the enormous amount of storage required.
Pokeman Stadium
Although the N64 had only a few games available when it first came out, the number of titles has grown to a considerable library. Used games can be found for less than $15. Many of the new games can cost between $50 and $75.
,A
