introduction to computer network

uses of computer networks

1-business applications

most companies have a substantial number of computers. for example, a company may have a computer for each worker and use them to design products, write brochures, and do the payroll. initially, some of these computers may have worked in isolation from the others, but at some point, management may have decided to connect them to be able to distribute information throughout the company.
put in slightly more general form, the issue here is resource sharing. the goal is to make all programs, equipment, and especially data available to anyone on the network without regard to the physical location of the resource or the user.
an obvious and widespread example is having a group of office workers share a common printer. none of the individuals really needs a private printer, and a high-volume networked printer is often cheaper, faster, and easier to maintain than a large collection of individual printers.
in the simplest of terms, one can imagine a company’s information system as consisting of one or more databases with company information and some number of employees who need to access them remotely. in this model, the data are stored on powerful computers called servers. often these are centrally housed and maintained by a system administrator. in contrast, the employees have simpler machines, called clients, on their desks, with which they access remote data, for example, to include in spreadsheets they are constructing. (sometimes we will refer to the human user of the client machine as the ‘‘client,’’ but it should be clear from the context whether we mean the computer or its user.) the client and server machines are connected by a network, as illustrated in fig. 1-1. note that we have shown the network as a simple oval, without any detail. we will use this form when we mean a network in the most abstract sense. when more detail is required, it will be provided.




this whole arrangement is called the client-server model. it is widely used and forms the basis of much network usage. the most popular realization is that of a web application, in which the server generates web pages based on its database in response to client requests that may updating the database. the client-server model is applicable when the client and server are both in the same building (and belong to the same company), but also when they are far apart. for example, when a person at home accesses a page on the world wide web, the same model is employed, with the remote web server being the server and the user’s personal computer being the client. under most conditions, one server can handle a large number (hundreds or thousands) of clients simultaneously.
if we look at the client-server model in detail, we see that two processes (i.e., running programs) are involved, one on the client machine and one on the server machine. communication takes the form of the client process sending a message over the network to the server process. the client process then waits for a reply message. when the server process gets the request, it performs the requested work or looks up the requested data and sends back a reply. these messages are shown in fig. 1-2.


a second goal of setting up a computer network has to do with people rather than information or even computers. a computer network can provide a powerful communication medium among employees. virtually every company that has two or more computers now has email (electronic mail), which employees generally use for a great deal of daily communication. in fact, a common gripe around the water cooler is how much email everyone has to deal with, much of it quite meaningless because bosses have discovered that they can send the same (often content-free) message to all their subordinates at the push of a button. telephone calls between employees may be carried by the computer network instead of by the phone company. this technology is called ip telephony or voice over ip (voip) when internet technology is used. the microphone and speaker at each end may belong to a voip-enabled phone or the employee’s computer. companies find this a wonderful way to save on their telephone bills.

a third goal for many companies is doing business electronically, especially with customers and suppliers. this new model is called e-commerce (electronic commerce) and it has grown rapidly in recent years. airlines, bookstores, and other retailers have discovered that many customers like the convenience of shopping from home. consequently, many companies provide catalogs of their goods and services online and take orders online. manufacturers of automobiles, aircraft, and computers, among others, buy subsystems from a variety of suppliers and then assemble the parts. using computer networks, manufacturers can place orders electronically as needed. this reduces the need for large inventories and enhances efficiency.


2-home applications

internet access provides home users with connectivity to remote computers. as with companies, home users can access information, communicate with other people, and buy products and services with e-commerce. access to remote information comes in many forms. it can be surfing the world wide web for information or just for fun. information available includes the arts, business, cooking, government, health, history, hobbies, recreation, science, sports, travel, and many others. fun comes in too many ways to mention, plus some ways that are better left unmentioned.
much of this information is accessed using the client-server model, but there is different, popular model for accessing information that goes by the name of peer-to-peer communication (parameswaran et al., 2001). in this form, individuals who form a loose group can communicate with others in the group, as shown in fig. 1-3. every person can, in principle, communicate with one or more other people there is no fixed division into clients and servers.


legal applications for peer-to-peer communication also exist. these include fans sharing public domain music, families sharing photos and movies, and users downloading public software packages. in fact, one of the most popular internet applications of all, email, is inherently peer-to-peer. this form of communication is likely to grow considerably in the future.
all of the above applications involve interactions between a person and a remote database full of information. the second broad category of network use is person-to-person communication, basically the 21st century’s answer to the 19th century’s telephone. e-mail is already used on a daily basis by millions of people all over the world and its use is growing rapidly. it already routinely contains audio and video as well as text and pictures. smell may take a while. any teenager worth his or her salt is addicted to instant messaging. this facility, derived from the unix talk program in use since around 1970, allows two people to type messages at each other in real time. there are multi-person messaging services too, such as the twitter service that lets people send short text messages called ‘‘tweets’’ to their circle of friends or other willing audiences. between person-to-person communications and accessing information are social network applications. here, the flow of information is driven by the relationships that people declare between each other. one of the most popular social networking sites is facebook. it lets people updating their personal profiles and shares the updatings with other people who they have declared to be their friends. other social networking applications can make introductions via friends of friends, send news messages to friends such as twitter above, and much more.
even more loosely, groups of people can work together to create content. a wiki, for example, is a collaborative web site that the members of a community edit. the most famous wiki is the wikipedia, an encyclopedia anyone can edit, but there are thousands of other wikis.
our third category is electronic commerce in the broadest sense of the term. home shopping is already popular and enables users to inspect the online catalogs of thousands of companies. some of these catalogs are interactive, showing products from different viewpoints and in configurations that can be personalized.
our fourth category is entertainment. this has made huge strides in the home in recent years, with the distribution of music, radio and television programs, and movies over the internet beginning to rival that of traditional mechanisms. users can find, buy, and download mp3 songs and dvd-quality movies and add them to their personal collection. tv shows now reach many homes via iptv (ip television) systems that are based on ip technology instead of cable tv or radio transmissions. media streaming applications let users tune into internet radio stations or watch recent episodes of their favorite tv shows. naturally, all of this content can be moved around your house between different devices, displays and speakers, usually with a wireless network.

3- mobile users
mobile computers, such as laptop and handheld computers, are one of the fastest-growing segments of the computer industry. their sales have already overtaken those of desktop computers. why would anyone want one? people on the go often want to use their mobile devices to read and send email, tweet, watch movies, download music, play games, or simply to surf the web for information. they want to do all of the things they do at home and in the office. naturally, they want to do them from anywhere on land, sea or in the air.
connectivity to the internet enables many of these mobile uses. since having a wired connection is impossible in cars, boats, and airplanes, there is a lot of interest in wireless networks. cellular networks operated by the telephone companies are one familiar kind of wireless network that blankets us with coverage for mobile phones. wireless hotspots based on the 802.11 standard are another kind of wireless network for mobile computers. they have sprung up everywhere that people go, resulting in a patchwork of coverage at cafes, hotels, airports, schools, trains and planes. anyone with a laptop computer and a wireless modem can just turn on their computer on and be connected to the internet through the hotspot, as though the computer were plugged into a wired network.
wireless networks are of great value to fleets of trucks, taxis, delivery vehicles, and repairpersons for keeping in contact with their home base. for example, in many cities, taxi drivers are independent businessmen, rather than being employees of a taxi company. in some of these cities, the taxis have a display the driver can see. when a customer calls up, a central dispatcher types in the pickup and destination points. this information is displayed on the drivers’ displays and a beep sounds. the first driver to hit a button on the display gets the call.
wireless networks are also important to the military. if you have to be able to fight a war anywhere on earth at short notice, counting on using the local networking infrastructure is probably not a good idea. it is better to bring your own.
perhaps the key driver of mobile, wireless applications is the mobile phone. text messaging or texting is tremendously popular. it lets a mobile phone user type a short message that is then delivered by the cellular network to another mobile subscriber. few people would have predicted ten years ago that having teenagers tediously typing short text messages on mobile phones would be an immense money maker for telephone companies. but texting (or short message service as it is known outside the u.s.) is very profitable since it costs the carrier but a tiny fraction of one cent to relay a text message, a service for which they charge far more.
the long-awaited convergence of telephones and the internet has finally arrived, and it will accelerate the growth of mobile applications. smart phones, such as the popular iphone, combine aspects of mobile phones and mobile computers.
the (3g and 4g) cellular networks to which they connect can provide fast data services for using the internet as well as handling phone calls. many advanced phones connect to wireless hotspots too, and automatically switch between networks to choose the best option for the user. since mobile phones know their locations, often because they are equipped with gps (global positioning system) receivers, some services are intentionally location dependent. mobile maps and directions are an obvious candidate as your gps-enabled phone and car probably have a better idea of where you are than you do. so, too, are searches for a nearby bookstore or chinese restaurant, or a local weather forecast. other services may record location, such as annotating photos and videos with the place at which they were made. this annotation is known as ‘‘geo-tagging.’’
no doubt the uses of mobile and wireless computers will grow rapidly in the future as the size of computers shrinks, probably in ways no one can now foresee. let us take a quick look at some possibilities. sensor networks are made up of nodes that gather and wirelessly relay information they sense about the state of the physical world. the nodes may be part of familiar items such as cars or phones, or they may be small separate devices. for example, your car might gather data on its location, speed, vibration, and fuel efficiency from its on-board diagnostic system and upload this information to a database (hull et al., 2006). those data can help find potholes, plan trips around congested roads, and tell you if you are a ‘‘gas guzzler’’ compared to other drivers on the same stretch of road.
sensor networks are revolutionizing science by providing a wealth of data on behavior that could not previously be observed. one example is tracking the migration of individual zebras by placing a small sensor on each animal (juang et al., 2002). researchers have packed a wireless computer into a cube 1 mm on edge (warneke et al., 2001). with mobile computers this small, even small birds, rodents, and insects can be tracked.
wearable computers are another promising application. smart watches with radios have been part of our mental space since their appearance in the dick tracy comic strip in 1946 now you can buy them. other such devices may be implanted, such as pacemakers and insulin pumps. some of these can be controlled over a wireless network. this lets doctors test and reconfigure them more easily. it could also lead to some nasty problems if the devices are as insecure as the average pc and can be hacked easily

4-social issues
computer networks, like the printing press 500 years ago, allow ordinary citizens to distribute and view content in ways that were not previously possible. but along with the good comes the bad, as this new-found freedom brings with it many unsolved social, political, and ethical issues.
social networks, message boards, content sharing sites, and a host of other applications allow people to share their views with like-minded individuals. as long as the subjects are restricted to technical topics or hobbies like gardening, not too many problems will arise
network hardware
the network can be classified according to transmission technology and scale. broadly speaking, there are two types of transmission technology that are in widespread use: broadcast links and point-to-point links.

point-to-point links connect individual pairs of machines. to go from the source to the destination on a network made up of point-to-point links, short messages, called packets in certain contexts, may have to first visit one or more intermediate machines. often multiple routes, of different lengths, are possible, so finding good ones is important in point-to-point networks. point-to-point transmission with exactly one sender and exactly one receiver is sometimes called unicasting.

in contrast, on a broadcast network, the communication channel is shared by all the machines on the network packets sent by any machine are received by all the others. an address field within each packet specifies the intended recipient. upon receiving a packet, a machine checks the address field. if the packet is intended for the receiving machine, that machine processes the packet if the packet is intended for some other machine, it is just ignored.

broadcast systems usually also allow the possibility of addressing a packet to all destinations by using a special code in the address field. when a packet with this code is transmitted, it is received and processed by every machine on the network. this mode of operation is called broadcasting. some broadcast systems also support transmission to a subset of the machines, which known as multicasting.

an alternative criterion for classifying networks is by scale. distance is important as a classification metric because different technologies are used at different scales.

in figure below we classify multiple processor systems by their rough physical size. at the top are the personal area networks, networks that are meant for one person. beyond these come longer-range networks. these can be divided into local, metropolitan, and wide area networks, each with increasing scale. finally, the connection of two or more networks is called an internetwork. the worldwide internet is certainly the best-known (but not the only) example of an internetwork. soon we will have even larger internetworks with the interplanetary internet that connects networks across space.





















1-personal area networks

pans (personal area networks) let devices communicate over the range of a person. a common example is a wireless network that connects a computer with its peripherals. almost every computer has an attached monitor, keyboard, mouse, and printer. without using wireless, this connection must be done with cables. so many new users have a hard time finding the right cables and plugging them into the right little holes (even though they are usually color coded) that most computer vendors offer the option of sending a technician to the user’s home to do it. to help these users, some companies got together to design a short-range wireless network called bluetooth to connect these components without wires. the idea is that if your devices have bluetooth, then you need no cables. you just put them down, turn them on, and they work together. for many people, this ease of operation is a big plus.

in the simplest form, bluetooth networks use the master-slave paradigm of figure below. the system unit (the pc) is normally the master, talking to the mouse, keyboard, etc., as slaves. the master tells the slaves what addresses to use, when they can broadcast, how long they can transmit, what frequencies they can use, and so on.





















2-local area networks

a lan (local area network) is a privately owned network that operates within and nearby a single building. lans are widely used to connect personal computers and consumer electronics to let them share resources (e.g., printers) and exchange information.

wireless lans are very popular these days, especially in places where it is too much trouble to install cables. in these systems, every computer has a radio modem and an antenna that it uses to communicate with other computers. in most cases, each computer talks to a device in the ceiling as shown in figure below`. this device, called an ap (access point), wireless router, or base station, relays packets between the wireless computers and also between them and the internet. there is a standard for wireless lans called ieee 802.11, popularly known as wifi, which has become very widespread.

wired lans use a range of different transmission technologies. most of them use copper wires, but some use optical fiber. lans are restricted in size, which means that the worst-case transmission time is bounded and known in advance. the topology of many wired lans is built from point-to-point links. ieee 802.3, popularly called ethernet, is, by far, the most common type of wired lan. figure below shows a sample topology of switched ethernet. each computer speaks the ethernet protocol and connects to a box called a switch with a point-to-point link. a switch has multiple ports, each of which can connect to one computer. the job of the switch is to relay packets between computers that are attached to it, using the address in each packet to determine which computer to send it to.

3-metropolitan area networks
a man (metropolitan area network) covers a city. the best-known examples of mans are the cable television networks available in many cities. these systems grew from earlier community antenna systems used in areas with poor over-the-air television reception. in those early systems, a large antenna was placed on top of a nearby hill and a signal was then piped to the subscribers’ houses. cable television is not the only man, though. recent developments in high-speed wireless internet access have resulted in another man, which has been standardized as ieee 802.16 and is popularly known as wimax.
















4-wide area networks
a wan (wide area network) spans a large geographical area, often a country or continent. we will begin our discussion with wired wans, using the example of a company with branch offices in different cities. the wan in figure below is a network that connects offices in perth, melbourne, and brisbane. each of these offices contains computers intended for running user (i.e., application) programs. we will follow traditional usage and call these machines hosts. the rest of the network that connects these hosts is then called the communication subnet, or just subnet for short. the job of the subnet is to carry messages from host to host just as the telephone system carries words (really just sounds) from speaker to listener.

in most wans, the subnet consists of two distinct components: transmission lines and switching elements. transmission lines move bits between machines. they can be made of copper wire, optical fiber, or even radio links. most companies do not have transmission lines lying about, so instead they lease the lines from a telecommunications company. switching elements, or just switches, are specialized computers that connect two or more transmission lines. when data arrive on an incoming line, the switching element must choose an outgoing line on which to forward them. these switching computers have been called by various names in the past the name router is now most commonly used. unfortunately, some people pronounce it ‘‘rooter’’ while others have it rhyme with ‘‘doubter.’’



5-internetworks
many networks exist in the world, often with different hardware and software. people connected to one network often want to communicate with people attached to a different one. the fulfillment of this desire requires that different, and frequently incompatible, networks be connected. a collection of interconnected networks is called an internetwork or internet. the internet uses isp networks to connect enterprise networks, home networks, and many other networks.

subnets, networks, and internetworks are often confused. the term ‘‘subnet’’ makes the most sense in the context of a wide area network, where it refers to the collection of routers and communication lines owned by the network operator. as an analogy, the telephone system consists of telephone switching offices connected to one another by high-speed lines, and to houses and businesses by low-speed lines. these lines and equipment, owned and managed by the telephone company, form the subnet of the telephone system. the telephones themselves (the hosts in this analogy) are not part of the subnet. a network is formed by the combination of a subnet and its hosts. however, the word ‘‘network’’ is often used in a loose sense as well. we know that an internet is formed when distinct networks are interconnected. in our view, connecting a lan and a wan or connecting two lans is the usual way to form an internetwork, but there is little agreement in the industry over terminology in this area.

there are two rules of thumb that are useful. first, if different organizations have paid to construct different parts of the network and each maintains its part, we have an internetwork rather than a single network. second, if the underlying technology is different in different parts (e.g., broadcast versus point-to-point and wired versus wireless), we probably have an internetwork.

network software
protocol hierarchies

to reduce their design complexity, most networks are organized as a stack of layers or levels, each one built upon the one below it. the number of layers, the name of each layer, the contents of each layer, and the function of each layer differ from network to network. the purpose of each layer is to offer certain services to the higher layers while shielding those layers from the details of how the offered services are actually implemented. in a sense, each layer is a kind of virtual machine, offering certain services to the layer above it. this concept is actually a familiar one and is used throughout computer science, where it is variously known as information hiding, abstract data types, data encapsulation, and object-oriented programming. the fundamental idea is that a particular piece of software (or hardware) provides a service to its users but keeps the details of its internal state and algorithms hidden from them. when layer n on one machine carries on a conversation with layer n on another machine, the rules and conventions used in this conversation are collectively known as the layer n protocol. basically, a protocol is an agreement between the communicating parties on how communication is to proceed.

a five-layer network is illustrated in figure below. the entities comprising the corresponding layers on different machines are called peers. the peers may be software processes, hardware devices, or even human beings. in other words, it is the peers that communicate by using the protocol to talk to each other.


in reality, no data are directly transferred from layer n on one machine to layer n on another machine. instead, each layer passes data and control information to the layer immediately below it, until the lowest layer is reached. below layer 1 is the physical medium through which actual communication occurs.

between each pair of adjacent layers is an interface. the interface defines which primitive operations and services the lower layer makes available to the upper one. when network designers decide how many layers to include in a network and what each one should do, one of the most important considerations is defining clean interfaces between the layers. doing so, in turn, requires that each layer perform a specific collection of well-understood functions. in addition to minimizing the amount of information that must be passed between layers, clear cut interfaces also make it simpler to replace one layer with a completely different protocol or implementation.

a set of layers and protocols is called a network architecture. the specification of an architecture must contain enough information to allow an implementer to write the program or build the hardware for each layer so that it will correctly obey the appropriate protocol. neither the details of the implementation nor the specification of the interfaces is part of the architecture because these are hidden away inside the machines and not visible from the outside. it is not even necessary that the interfaces on all machines in a network be the same, provided that each machine can correctly use all the protocols. a list of the protocols used by a certain system, one protocol per layer, is called a protocol stack.

now consider a more technical example: how to provide communication to the top layer of the five-layer network in figure below. a message, m, is produced by an application process running in layer 5 and given to layer 4 for transmission. layer 4 puts a header in front of the message to identify the message and passes the result to layer 3. the header includes control information, such as addresses, to allow layer 4 on the destination machine to deliver the message. other examples of control information used in some layers are sequence numbers (in case the lower layer does not preserve message order), sizes, and times.

in many networks, no limit is placed on the size of messages transmitted in the layer 4 protocol but there is nearly always a limit imposed by the layer 3 protocol. consequently, layer 3 must break up the incoming messages into smaller units, packets, prepending a layer 3 header to each packet. in this example, m is split into two parts, m1 and m2, that will be transmitted separately.

layer 3 decides which of the outgoing lines to use and passes the packets to layer 2. layer 2 adds to each piece not only a header but also a trailer, and gives the resulting unit to layer 1 for physical transmission. at the receiving machine the message moves upward, from layer to layer, with headers being stripped off as it progresses. none of the headers for layers below n are passed up to layer n.

design issues for the layers

reliability is the design issue of making a network that operates correctly even though it is made up of a collection of components that are themselves unreliable. think about the bits of a packet traveling through the network. there is a chance that some of these bits will be received damaged (inverted) due to fluke electrical noise, random wireless signals, hardware flaws, software bugs and so on.
one mechanism for finding errors in received information uses codes for error detection. information that is incorrectly received can then be retransmitted until it is received correctly. more powerful codes allow for error correction.
another reliability issue is finding a working path through a network. often there are multiple paths between a source and destination, and in a large network, there may be some links or routers that are broken. this topic is called routing.
a second design issue concerns the evolution of the network. since there are many computers on the network, every layer needs a mechanism for identifying the senders and receivers that are involved in a particular message. this mechanism is called addressing or naming, in the low and high layers, respectively.
an aspect of growth is that different network technologies often have different limitations. for example, not all communication channels preserve the order of messages sent on them, leading to solutions that number messages. another example is differences in the maximum size of a message that the networks can transmit. this leads to mechanisms for disassembling, transmitting, and then reassembling messages. this overall topic is called internetworking.
when networks get large, new problems arise. cities can have traffic jams, a shortage of telephone numbers, and it is easy to get lost. not many people have these problems in their own neighborhood, but citywide they may be a big issue. designs that continue to work well when the network gets large are said to be scalable.
a third design issue is resource allocation. networks provide a service to hosts from their underlying resources, such as the capacity of transmission lines. to do this well, they need mechanisms that divide their resources so that one host does not interfere with another too much. many designs share network bandwidth dynamically, according to the short term needs of hosts, rather than by giving each host a fixed fraction of the bandwidth that it may or may not use. this design is called statistical multiplexing, meaning sharing based on the statistics of demand. it can be applied at low layers for a single link, or at high layers for a network or even applications that use the network.
an allocation problem that occurs at every level is how to keep a fast sender from swamping a slow receiver with data. feedback from the receiver to the sender is often used. this subject is called flow control. sometimes the problem is that the network is oversubscribed because too many computers want to send too much traffic, and the network cannot deliver it all. this overloading of the network is called congestion. one strategy is for each computer to reduce its demand when it experiences congestion.
it is interesting to observe that the network has more resources to offer than simply bandwidth. for uses such as carrying live video, the timeliness of delivery matters a great deal. most networks must provide service to applications that want this real-time delivery at the same time that they provide service to applications that want high throughput. quality of service is the name given to mechanisms that reconcile these competing demands.
the last major design issue is to secure the network by defending it against different kinds of threats. one of the threats we have mentioned previously is that of eavesdropingping on communications. mechanisms that provide confidentiality defend against this threat, and they are used in multiple layers. mechanisms for authentication prevent someone from impersonating someone else. they might be used to tell fake banking web sites from the real one, or to let the cellular network check that a call is really coming from your phone so that you will pay the bill. other mechanisms for integrity prevent surreptitious changes to messages. all of these designs are based on cryptography
connection-oriented versus connectionless service
layers can offer two different types of service to the layers above them: connection-oriented and connectionless. connection-oriented service is modeled after the telephone system. to talk to someone, you pick up the phone, dial the number, talk, and then hang up. similarly, to use a connection-oriented network service, the service user first establishes a connection, uses the connection, and then releases the connection. the essential aspect of a connection is that it acts like a tube: the sender pushes objects (bits) in at one end, and the receiver takes them out at the other end. in most cases the order is preserved so that the bits arrive in the order they were sent.
in some cases when a connection is established, the sender, receiver, and subnet conduct a negotiation about the parameters to be used, such as maximum message size, quality of service required, and other issues. typically, one side makes a proposal and the other side can accept it, reject it, or make a counterproposal.
a circuit is another name for a connection with associated resources, such as a fixed bandwidth. this dates from the telephone network in which a circuit was a path over copper wire that carried a phone conversation. in contrast to connection-oriented service, connectionless service is modeled after the postal system. each message (letter) carries the full destination address, and each one is routed through the intermediate nodes inside the system independent of all the subsequent messages. there are different names for messages in different contexts a packet is a message at the network layer. when the intermediate nodes receive a message in full before sending it on to the next node, this is called store-and-forward switching. the alternative, in which the onward transmission of a message at a node starts before it is completely received by the node, is called cut-through switching. normally, when two messages are sent to the same destination, the first one sent will be the first one to arrive. however, it is possible that the first one sent can be delayed so that the second one arrives first.










reference models

now that we have discussed layered networks in the abstract, it is time to look at some examples. we will discuss two important network architectures: the osi reference model and the tcp/ip reference model. although the protocols associated with the osi model are not used any more, the model itself is actually quite general and still valid, and the features discussed at each layer are still very important. the tcp/ip model has the opposite properties: the model itself is not of much use but the protocols are widely used.

the osi reference model

the osi model is shown in figure below. this model is based on a proposal developed by the international standards organization (iso) as a first step toward international standardization of the protocols used in the various layers. it was revised in 1995. the model is called the iso osi (open systems interconnection) reference model because it deals with connecting open systems—that is, systems that are open for communication with other systems. we will just call it the osi model for short.

the physical layer
the physical layer is concerned with transmitting raw bits over a communication channel. the design issues have to do with making sure that when one side sends a 1 bit it is received by the other side as a 1 bit, not as a 0 bit. typical questions here are what electrical signals should be used to represent a 1 and a 0, how many nanoseconds a bit lasts, whether transmission may proceed simultaneously in both directions, how the initial connection is established, how it is torn down when both sides are finished, how many pins the network connector has, and what each pin is used for. these design issues largely deal with mechanical, electrical, and timing interfaces, as well as the physical transmission medium, which lies below the physical layer.

the data link layer
the main task of the data link layer is to transform a raw transmission facility into a line that appears free of undetected transmission errors. it does so by masking the real errors so the network layer does not see them. it accomplishes this task by having the sender break up the input data into data frames (typically a few hundred or a few thousand bytes) and transmit the frames sequentially. if the service is reliable, the receiver confirms correct receipt of each frame by sending back an acknowledgement frame.
another issue that arises in the data link layer is how to keep a fast transmitter from drowning a slow receiver in data. some traffic regulation mechanism may be needed to let the transmitter know when the receiver can accept more data. broadcast networks have an additional issue in the data link layer: how to control access to the shared channel. a special sublayer of the data link layer, the medium access control sublayer, deals with this problem.

the network layer
the network layer controls the operation of the subnet. a key design issue is determining how packets are routed from source to destination. routes can be based on static tables that are ‘‘wired into’’ the network and rarely changed, or more often they can be updatingd automatically to avoid failed components. they can also be determined at the start of each conversation. finally, they can be highly dynamic, being determined anew for each packet to reflect the current network load. if too many packets are present in the subnet at the same time, they will get in one another’s way, forming bottlenecks. handling congestion is also a responsibility of the network layer, in conjunction with higher layers that adapt the load they place on the network. more generally, the quality of service provided (delay, transit time, jitter, etc.) is also a network layer issue. in broadcast networks, the routing problem is simple, so the network layer is often thin or even nonexistent.

the transport layer
the basic function of the transport layer is to accept data from above it, split it up into smaller units if need be, pass these to the network layer, and ensure that the pieces all arrive correctly at the other end. the most popular type of transport connection is an error-free point-to-point channel that delivers messages or bytes in the order in which they were sent. however, other possible kinds of transport service exist, such as the transporting of isolated messages with no guarantee about the order of delivery, and the broadcasting of messages to multiple destinations. the type of service is determined when the connection is established.
the transport layer is a true end-to-end layer it carries data all the way from the source to the destination. in other words, a program on the source machine carries on a conversation with a similar program on the destination machine, using the message headers and control messages. in the lower layers, each protocols is between a machine and its immediate neighbors, and not between the ultimate source and destination machines, which may be separated by many routers.

the session layer
the session layer allows users on different machines to establish sessions between them. sessions offer various services, including dialog control (keeping track of whose turn it is to transmit), token management (preventing two parties from attempting the same critical operation simultaneously), and synchronization (check pointing long transmissions to allow them to pick up from where they left off in the event of a crash and subsequent recovery).

the presentation layer
unlike the lower layers, which are mostly concerned with moving bits around, the presentation layer is concerned with the syntax and semantics of the information transmitted. in order to make it possible for computers with different internal data representations to communicate, the data structures to be exchanged can be defined in an abstract way, along with a standard encoding to be used ‘‘on the wire.’’ the presentation layer manages these abstract data structures and allows higher-level data structures (e.g., banking records) to be defined and exchanged.

the application layer
the application layer contains a variety of protocols that are commonly needed by users. one widely used application protocol is http (hyper text transfer protocol), which is the basis for the world wide web. when a browser wants a web page, it sends the name of the page it wants to the server hosting the page using http. the server then sends the page back. other application protocols are used for file transfer, electronic mail, and network news.

tcp/ip model
the first layered protocol model for internetwork communications was created in the early 1970s and is referred to as the internet model, tcp/ip is stand for transmission control protocol and internet protocol. it defines four layers that must occur for communications to be successful that illustrated in figure below:

these protocols, which are implemented on both the sending and receiving hosts, interact to provide end-to-end delivery of applications over a network.

the link layer
all these requirements led to the choice of a packet-switching network based on a connectionless layer that runs across different networks. the lowest layer in the model, the link layer describes what links such as serial lines and classic ethernet must do to meet the needs of this connectionless internet layer. it is not really a layer at all, in the normal sense of the term, but rather an interface between hosts and transmission links. early material on the tcp/ip model has little to say about it.

the internet layer
the internet layer is the linchpin that holds the whole architecture together. it is shown in figure below as corresponding roughly to the osi network layer. its job is to permit hosts to inject packets into any network and have them travel independently to the destination (potentially on a different network). they may even arrive in a completely different order than they were sent, in which case it is the job of higher layers to rearrange them, if in-order delivery is desired.


the internet layer defines an official packet format and protocol called ip
(internet protocol), plus a companion protocol called icmp (internet control message protocol) that helps it function. the job of the internet layer is to deliver ip packets where they are supposed to go. packet routing is clearly a major issue here, as is congestion (though ip has not proven effective at avoiding congestion).

the transport layer
the layer above the internet layer in the tcp/ip model is now usually called the transport layer. it is designed to allow peer entities on the source and destination hosts to carry on a conversation, just as in the osi transport layer. two end-to-end transport protocols have been defined here. the first one, tcp (transmission control protocol), is a reliable connection-oriented protocol that allows a byte stream originating on one machine to be delivered without error on any other machine in the internet. it segments the incoming byte stream into discrete messages and passes each one on to the internet layer. at the destination, the receiving tcp process reassembles the received messages into the output stream. tcp also handles flow control to make sure a fast sender cannot swamp a slow receiver with more messages than it can handle. the second protocol in this layer, udp (user datagram protocol), is an unreliable, connectionless protocol for applications that do not want tcp’s sequencing or flow control and wish to provide their own. it is also widely used for one-shot, client-server-type request-reply queries and applications in which prompt delivery is more important than accurate delivery, such as transmitting speech or video. the relation of ip, tcp, and udp is shown in figure below. since the model was developed, ip has been implemented on many other networks.



the application layer
the tcp/ip model does not have session or presentation layers. no need for them was perceived. instead, applications simply include any session and presentation functions that they require. experience with the osi model has proven this view correct: these layers are of little use to most applications. on top of the transport layer is the application layer. it contains all the higher-level protocols. the early ones included virtual terminal (telnet), file transfer (ftp), and electronic mail (smtp). many other protocols have been added to these over the years. some important ones that we will study, shown in figure above.


network media
communication across a network is carried on a medium. the medium provides the channel over which the message travels from source to destination.
modern networks primarily use three types of media to interconnect devices and to provide the pathway over which data can be transmitted. these media are:
• metallic wires within cables (twisted pair, coaxial cable)
• glass or plastic fibers (fiber optic cable)
• wireless transmission
the signal encoding that must occur for the message to be transmitted is different for each media type. on metallic wires, the data is encoded into electrical impulses that match specific patterns. fiber optic transmissions rely on pulses of light, within either infrared or visible light ranges. in wireless transmission, patterns of electromagnetic waves depict the various bit values.

twisted-pair wires:
this type consists of two insulated copper wires, typically about 1mm thick. the wires are twisted together in a spiral form. the purpose of twisting the wires is to reduce electrical interference from similar pairs or from outside noise. there are two kinds of twisted pairs:
• unshielded twisted pair (utp): it consists of two wires that are twisted together within insulated outside covering. utp suffer from the interruption of the data communication signals caused by the radio frequency interference or electromagnetic interference.
• shielded twisted pair (stp) cable: consists of pairs of insulated solid wire surrounded by a braided or corrugated shielding. stp reduces the interruption of the data communication signals caused by the radio frequency interference or electromagnetic interference. the superiority of stp over utp came from that stp
- give better noise immunity.
- support a long distance transmission quality.
- provide high-speed transmission

utp cable stp cable
coaxial cables:
a coaxial cable consists of a stiff copper wire as the core, surrounded by an insulating material. the insulator is encased by a cylindrical conductor, often as a closely woven braided mesh. the outer conductor is covered in a protective plastic sheath. a coaxial cable is much less susceptible to electromagnetic interference and can carry much more data than the twisted pair wires. because of this, it is used to carry high-speed data traffic as well television signals.

coaxial cable
there are two types of coaxial cable:
• thin coaxial cable: bus network with diameter 0.6 cm and runs ethernet media access up to 185 meters and used in 10base2 networks.
• thick coaxial cable: bus network with diameter 1.2 cm and runs ethernet up to 500 meters and used in 10base5 networks.

optical fiber cables:
optical fiber consists of a thin core made of glass or plastic, surrounded by a cladding, also glass or plastic, but with different properties from the core and finally there is a protective jacket (plastic). in general, light confined to the central core by a phenomenon called total internal reflection, whereby it cannot escape through the discontinuity in optical properties at the core-cladding interface.


(a) view of a single fiber. (b) end view of a sheath with three fibers.
fiber optic cable can carry huge amounts of information at fast data rates. there are two modes (multi-mode and single mode) for propagating light along optical channels, each requiring fiber with different physical characteristics.

advantages of fiber optic cable
• they have far superior electromagnetic isolation and more resistance to noise.
• the attenuation rates are very low.
• the transmission speed of data is very high and carries the data for long distances.
• in optical fiber, the digital data transformed to light pulses, this leads to prevent the electrical signal to pass through these fibers. this provides a good security.
disadvantages of fiber optic cable:
• it is most expensive.
• the energy of the light pulse reduced through the propagation, due to absorption and scattering.
wireless transmission media:
electromagnetic waves ranging in frequencies between 3 khz and 1 ghz are normally called radio waves waves ranging in frequencies between 1 and 300 ghz are called microwaves

1. radio transmission:
it is electromagnetic waves can also be broadcast through free space and some material media such as air. carrier of these frequencies is used to transmit audio, digital baseband, and video by means of modulation. the range of radio carrier frequencies is divided into a number of bands as follows:



2- the microwaves:
microwaves may be guided using hollow metal tubes called waveguides. microwaves can be transmitted directionally through space using special antenna (such as parabolic dish. the microwave travel in straight line. unlike radio waves at lower frequencies, microwaves do not pass through building well. microwave communication is widely used for long distance telephone communication, cellular telephones, and television distribution.
3- the infrared waves:
it is widely used for short-range communication (e.g., the remote control that used on the tv). it is cheap and easy to build, but the major drawback: it does not pass through solid objects. it is used in the local network inside the building.
4- the light wave transmission:
it is unguided optical signaling. a most modern application is to connect the local networks in two buildings via lasers mounted on their rooftops. coherent optical signaling using lasers is inherently unidirectional, so each building needs its own laser and its own photo detector. this scheme offers very high bandwidth and very low costs. a disadvantage is that laser beams cannot penetrate rain or thick fog, but they work well on sunny days.

data link layer design issues
the data link layer uses the services of the physical layer to send and receive bits over communication channels. it has a number of functions, including:
1. providing a well-defined service interface to the network layer.
2. dealing with transmission errors.
3. regulating the flow of data so that fast senders do not swamp slow receivers.
to accomplish these goals, the data link layer takes the packets it gets from the network layer and encapsulates them into frames for transmission. each frame contains a frame header, a payload field for holding the packet, and a frame trailer, as illustrated in figure below. frame management forms the heart of what the data link layer does.

services provided to the network layer
the function of the data link layer is to provide services to the network layer. the principal service is transferring data from the network layer on the source machine to the network layer on the destination machine. on the source machine is an entity, call it a process, in the network layer that hands some bits to the data link layer for transmission to the destination. the job of the data link layer is to transmit the bits to the destination machine so they can be handed over to the network layer there, as shown in figure (a) below. the actual transmission follows the path of figure (b), but it is easier to think in terms of two data link layer processes communicating using a data link protocol. for this reason, we will implicitly use the model of figure (a) below.


the data link layer can be designed to offer various services. the actual services that are offered vary from protocol to protocol. three reasonable possibilities that we will consider in turn are:
1. unacknowledged connectionless service.
2. acknowledged connectionless service.
3. acknowledged connection-oriented service.

unacknowledged connectionless service consists of having the source machine send independent frames to the destination machine without having the destination machine acknowledge them. ethernet is a good example of a data link layer that provides this class of service. no logical connection is established beforehand or released afterward. if a frame is lost due to noise on the line, no attempt is made to detect the loss or recover from it in the data link layer. this class of service is appropriate when the error rate is very low, so recovery is left to higher layers. it is also appropriate for real-time traffic, such as voice, in which late data are worse than bad data.

the next step up in terms of reliability is acknowledged connectionless service. when this service is offered, there are still no logical connections used, but each frame sent is individually acknowledged. in this way, the sender knows whether a frame has arrived correctly or been lost. if it has not arrived within a specified time interval, it can be sent again. this service is useful over unreliable channels, such as wireless systems. 802.11 (wifi) is a good example of this class of service. it is perhaps worth emphasizing that providing acknowledgements in the data link layer is just an optimization, never a requirement.

the network layer can always send a packet and wait for it to be acknowledged by its peer on the remote machine. if the acknowledgement is not forthcoming before the timer expires, the sender can just send the entire message again. the trouble with this strategy is that it can be inefficient. links usually have a strict maximum frame length imposed by the hardware, and known propagation delays. the network layer does not know these parameters. it might send a large packet that is broken up into, say, 10 frames, of which 2 are lost on average. it would then take a very long time for the packet to get through. instead, if individual frames are acknowledged and retransmitted, then errors can be corrected more directly and more quickly. on reliable channels, such as fiber, the overhead of a heavyweight data link protocol may be unnecessary, but on (inherently unreliable) wireless channels it is well worth the cost.
getting back to our services, the most sophisticated service the data link layer can provide to the network layer is connection-oriented service. with this service, the source and destination machines establish a connection before any data are transferred. each frame sent over the connection is numbered, and the data link layer guarantees that each frame sent is indeed received. furthermore, it guarantees that each frame is received exactly once and that all frames are received in the right order. connection-oriented service thus provides the network layer processes with the equivalent of a reliable bit stream. it is appropriate over long, unreliable links such as a satellite channel or a long-distance telephone circuit. if acknowledged connectionless service were used, it is conceivable that lost acknowledgements could cause a frame to be sent and received several times, wasting bandwidth.

when connection-oriented service is used, transfers go through three distinct phases. in the first phase, the connection is established by having both sides initialize variables and counters needed to keep track of which frames have been received and which ones have not. in the second phase, one or more frames are actually transmitted. in the third and final phase, the connection is released, freeing up the variables, buffers, and other resources used to maintain the connection.
framing
to provide service to the network layer, the data link layer must use the service provided to it by the physical layer. what the physical layer does is accept a raw bit stream and attempt to deliver it to the destination. if the channel is noisy, as it is for most wireless and some wired links, the physical layer will add some redundancy to its signals to reduce the bit error rate to a tolerable level. however, the bit stream received by the data link layer is not guaranteed to be error free. some bits may have different values and the number of bits received may be less than, equal to, or more than the number of bits transmitted. it is up to the data link layer to detect and, if necessary, correct errors.

the usual approach is for the data link layer to break up the bit stream into discrete frames, compute a short token called a checksum for each frame, and include the checksum in the frame when it is transmitted. when a frame arrives at the destination, the checksum is recomputed. if the newly computed checksum is different from the one contained in the frame, the data link layer knows that an error has occurred and takes steps to deal with it (e.g., discarding the bad frame and possibly also sending back an error report). breaking up the bit stream into frames is more difficult than it at first appears.
a good design must make it easy for a receiver to find the start of new frames while using little of the channel bandwidth. we will look at four methods:
1. byte count.
2. flag bytes with byte stuffing.
3. flag bits with bit stuffing.
4. physical layer coding violations.

the first framing method uses a field in the header to specify the number of bytes in the frame. when the data link layer at the destination sees the byte count, it knows how many bytes follow and hence where the end of the frame is. this technique is shown in figure (a) below for four small example frames of sizes 5, 5, 8, and 8 bytes, respectively. the trouble with this algorithm is that the count can be garbled by a transmission error. for example, if the byte count of 5 in the second frame of figure (b) becomes a 7 due to a single bit flip, the destination will get out of synchronization. it will then be unable to locate the correct start of the next frame. even if the checksum is incorrect so the destination knows that the frame is bad, it still has no way of telling where the next frame starts. sending a frame back to the source asking for a retransmission does not help either, since the destination does not know how many bytes to skip over to get to the start of the retransmission. for this reason, the byte count method is rarely used by itself.


the second framing method gets around the problem of resynchronization after an error by having each frame start and end with special bytes. often the same byte, called a flag byte, is used as both the starting and ending delimiter. this byte is shown in figure (a) below as flag. two consecutive flag bytes indicate the end of one frame and the start of the next. thus, if the receiver ever loses synchronization it can just search for two flag bytes to find the end of the current frame and the start of the next frame.

however, there is a still a problem we have to solve. it may happen that the flag byte occurs in the data, especially when binary data such as photographs or songs are being transmitted. this situation would interfere with the framing. one way to solve this problem is to have the sender’s data link layer insert a special escape byte (esc) just before each ‘‘accidental’’ flag byte in the data. thus, a framing flag byte can be distinguished from one in the data by the absence or presence of an escape byte before it. the data link layer on the receiving end removes the escape bytes before giving the data to the network layer. this technique is called byte stuffing. of course, the next question is: what happens if an escape byte occurs in the middle of the data? the answer is that it, too, is stuffed with an escape byte. at the receiver, the first escape byte is removed leaving the data byte that follows it (which might be another escape byte or the flag byte). some examples are shown in figure (b). in all cases, the byte sequence delivered after de-stuffing is exactly the same as the original byte sequence. we can still search for a frame boundary by looking for two flag bytes in a row, without bothering to undo escapes.


the third method of delimiting the bit stream gets around a disadvantage of byte stuffing, which is that it is tied to the use of 8-bit bytes. framing can be also be done at the bit level, so frames can contain an arbitrary number of bits made up of units of any size. it was developed for the once very popular hdlc (high level data link control) protocol. each frame begins and ends with a special bit pattern, 01111110 or 0x7e in hexadecimal. this pattern is a flag byte. whenever the sender’s data link layer encounters five consecutive 1s in the data, it automatically stuffs a 0 bit into the outgoing bit stream. this bit stuffing is analogous to byte stuffing, in which an escape byte is stuffed into the outgoing character stream before a flag byte in the data. it also ensures a minimum density of transitions that help the physical layer maintain synchronization. usb (universal serial bus) uses bit stuffing for this reason. when the receiver sees five consecutive incoming 1 bits, followed by a 0 bit, it automatically destuffs (i.e., deletings) the 0 bit. just as byte stuffing is completely transparent to the network layer in both computers, so is bit stuffing. if the user data contain the flag pattern, 01111110, this flag is transmitted as 011111010 but stored in the receiver’s memory as 01111110. figure 3-5 gives an example of bit stuffing.

with bit stuffing, the boundary between two frames can be unambiguously recognized by the flag pattern. thus, if the receiver loses track of where it is, all it has to do is scan the input for flag sequences, since they can only occur at frame boundaries and never within the data.

with both bit and byte stuffing, a side effect is that the length of a frame now depends on the contents of the data it carries. for instance, if there are no flag bytes in the data, 100 bytes might be carried in a frame of roughly 100 bytes. if, however, the data consists solely of flag bytes, each flag byte will be escaped and the frame will become roughly 200 bytes long. with bit stuffing, the increase would be roughly 12.5% as 1 bit is added to every byte.

the last method of framing is to use a shortcut from the physical layer. the encoding of bits as signals often includes redundancy to help the receiver. this redundancy means that some signals will not occur in regular data. we can use some reserved signals to indicate the start and end of frames. in effect, we are using ‘‘coding violations’’ to delimit frames.

the beauty of this scheme is that, because they are reserved signals, it is easy to find the start and end of frames and there is no need to stuff the data. many data link protocols use a combination of these methods for safety. a common pattern used for ethernet and 802.11 is to have a frame begin with a well-defined pattern called a preamble. this pattern might be quite long (72 bits is typical for 802.11) to allow the receiver to prepare for an incoming packet. the preamble is then followed by a length (i.e., count) field in the header that is used to locate the end of the frame.



error detection and correction
network designers have developed two basic strategies for dealing with errors. both add redundant information to the data that is sent. one strategy is to include enough redundant information to enable the receiver to deduce what the transmitted data must have been. the other is to include only enough redundancy to allow the receiver to deduce that an error has occurred (but not which error) and have it request a retransmission. the former strategy uses error-correcting codes and the latter uses error-detecting codes. the use of error-correcting codes is often referred to as fec (forward error correction).
error-correcting codes

four different error-correcting codes:
1. hamming codes.
2. binary convolutional codes.
3. reed-solomon codes.
4. low-density parity check codes.

all of these codes add redundancy to the information that is sent. a frame consists of m data (i.e., message) bits and r redundant (i.e. check) bits. in a block code, the r check bits are computed solely as a function of the m data bits with which they are associated, as though the m bits were looked up in a large table to find their corresponding r check bits. in a systematic code, the m data bits are sent directly, along with the check bits, rather than being encoded themselves before they are sent. in a linear code, the r check bits are computed as a linear function of the m data bits. exclusive or (xor) or modulo 2 addition is a popular choice. this means that encoding can be done with operations such as matrix multiplications or simple logic circuits.

let the total length of a block be n (i.e., n = m + r). we will describe this as an (n,m) code. an n-bit unit containing data and check bits is referred to as an n bit codeword. the code rate, or simply rate, is the fraction of the codeword that carries information that is not redundant, or m/n. the rates used in practice vary widely. they might be 1/2 for a noisy channel, in which case half of the received information is redundant, or close to 1 for a high-quality channel, with only a small number of check bits added to a large message. to understand how errors can be handled, it is necessary to first look closely at what an error really is. given any two codewords that may be transmitted or received—say, 10001001 and 10110001—it is possible to determine how many corresponding bits differ. in this case, 3 bits differ. to determine how many bits differ, just xor the two codewords and count the number of 1 bits in the result.


for example:
10001001
10110001

00111000
the number of bit positions in which two codewords differ is called the hamming distance. its significance is that if two codewords are a hamming distance d apart, it will require d single-bit errors to convert one into the other. given the algorithm for computing the check bits, it is possible to construct a complete list of the legal codewords, and from this list to find the two codewords with the smallest hamming distance. this distance is the hamming distance of the complete code.
in most data transmission applications, all 2m possible data messages are legal, but due to the way the check bits are computed, not all of the 2n possible codewords are used. in fact, when there are r check bits, only the small fraction of 2m /2n or 1/2r of the possible messages will be legal codewords. it is the sparseness with which the message is embedded in the space of codewords that allows the receiver to detect and correct errors. the error-detecting and error-correcting properties of a block code depend on its hamming distance. to reliably detect d errors, you need a distance d + 1 code because with such a code there is no way that d single-bit errors can change a valid codeword into another valid codeword. when the receiver sees an illegal codeword, it can tell that a transmission error has occurred. similarly, to correct d errors, you need a distance 2d + 1 code because that way the legal codewords are so far apart that even with d changes the original codeword is still closer than any other codeword. this means the original codeword can be uniquely determined based on the assumption that a larger number of errors are less likely. as a simple example of an error-correcting code, consider a code with only four valid codewords:
0000000000, 0000011111, 1111100000, and 1111111111

this code has a distance of 5, which means that it can correct double errors or detect quadruple errors. if the codeword 0000000111 arrives and we expect only single- or double-bit errors, the receiver will know that the original must have been 0000011111. if, however, a triple error changes 0000000000 into 0000000111, the error will not be corrected properly. alternatively, if we expect all of these errors, we can detect them. none of the received codewords are legal codewords so an error must have occurred. it should be apparent that in this example we cannot both correct double errors and detect quadruple errors because this would require us to interpret a received codeword in two different ways.

imagine that we want to design a code with m message bits and r check bits that will allow all single errors to be corrected. each of the 2m legal messages has n illegal codewords at a distance of 1 from it. these are formed by systematically inverting each of the n bits in the n-bit codeword formed from it. thus, each of the 2m legal messages requires n + 1 bit patterns dedicated to it. since the total number of bit patterns is 2n, we must have (n + 1)2m ? 2n. using n = m + r, this requirement becomes
(m + r + 1) ? 2r

in hamming codes the bits of the codeword are numbered consecutively, starting with bit 1 at the left end, bit 2 to its immediate right, and so on. the bits that are powers of 2 (1, 2, 4, 8, 16, etc.) are check bits. the rest (3, 5, 6, 7, 9, etc.) are filled up with the m data bits. this pattern is shown for an (11,7) hamming code with 7 data bits and 4 check bits in figure below. each check bit forces the modulo 2 sum, or parity, of some collection of bits, including itself, to be even (or odd). a bit may be included in several check bit computations. to see which check bits the data bit in position k contributes to, rewrite k as a sum of powers of 2. for example, 11 = 1 + 2 + 8 and 29 = 1 + 4 + 8 + 16. a bit is checked by just those check bits occurring in its expansion (e.g., bit 11 is checked by bits 1, 2, and 8). in the example, the check bits are computed for even parity sums for a message that is the ascii letter ‘‘a.’

this construction gives a code with a hamming distance of 3, which means that it can correct single errors (or detect double errors). the reason for the very careful numbering of message and check bits becomes apparent in the decoding process. when a codeword arrives, the receiver redoes the check bit computations including the values of the received check bits. we call these the check results. if the check bits are correct then, for even parity sums, each check result should be zero. in this case the codeword is accepted as valid.
if the check results are not all zero, however, an error has been detected. the set of check results forms the error syndrome that is used to pinpoint and correct the error. in fig. 3-6, a single-bit error occurred on the channel so the check results are 0, 1, 0, and 1 for k = 8, 4, 2, and 1, respectively. this gives a syndrome of 0101 or 4 + 1=5. by the design of the scheme, this means that the fifth bit is in error. flipping the incorrect bit (which might be a check bit or a data bit) and discarding the check bits gives the correct message of an ascii ‘‘a.’’

in a convolutional code, an encoder processes a sequence of input bits and generates a sequence of output bits. there is no natural message size or encoding boundary as in a block code. the output depends on the current and previous input bits. that is, the encoder has memory. the number of previous bits on which the output depends is called the constraint length of the code. convolutional codes are specified in terms of their rate and constraint length. convolutional codes are widely used in deployed networks, for example, as part of the gsm mobile phone system, in satellite communications, and in 802.11. as an example, a popular convolutional code is shown in figure below. this code is known as the nasa convolutional code of r = 1/2 and k = 7, since it was first used for the voyager space missions starting in 1977. since then it has been liberally reused, for example, as part of 802.11.



each input bit on the left-hand side produces two output bits on the right-hand side that are xor sums of the input and internal state. since it deals with bits and performs linear operations, this is a binary, linear convolutional code. since 1 input bit produces 2 output bits, the code rate is 1/2. it is not systematic since none of the output bits is simply the input bit.
the internal state is kept in six memory registers. each time another bit is input the values in the registers are shifted to the right. for example, if 111 is input and the initial state is all zeros, the internal state, written left to right, will become 100000, 110000, and 111000 after the first, second, and third bits have been input. the output bits will be 11, followed by 10, and then 01. it takes seven shifts to flush an input completely so that it does not affect the output. the constraint length of this code is thus k = 7.
reed-solomon codes are based on the fact that every n degree polynomial is uniquely determined by n + 1 points. for example, a line having the form ax + b is determined by two points. extra points on the same line are redundant, which is helpful for error correction. imagine that we have two data points that represent a line and we send those two data points plus two check points chosen to lie on the same line. if one of the points is received in error, we can still recover the data points by fitting a line to the received points. three of the points will lie on the line, and one point, the one in error, will not. by finding the line we have corrected the error.
reed-solomon codes are actually defined as polynomials that operate over finite fields, but they work in a similar manner. for m bit symbols, the codewords are 2m ?1 symbols long. a popular choice is to make m = 8 so that symbols are bytes. a codeword is then 255 bytes long. the (255, 233) code is widely used it adds 32 redundant symbols to 233 data symbols. decoding with error correction

in a ldpc (low-density parity check) code, each output bit is formed from only a fraction of the input bits. this leads to a matrix representation of the code that has a low density of 1s, hence the name for the code. the received codewords are decoded with an approximation algorithm that iteratively improves on a best fit of the received data to a legal codeword. this corrects errors. ldpc codes are practical for large block sizes and have excellent error-correction abilities that outperform many other codes (including the ones we have looked at) in practice. for this reason they are rapidly being included in new protocols. they are part of the standard for digital video broadcasting, 10 gbps ethernet, power-line networks, and the latest version of 802.11. expect to see more of them in future networks.
error-detecting codes
error-correcting codes are widely used on wireless links, which are notoriously noisy and error prone when compared to optical fibers. without error-correcting codes, it would be hard to get anything through. however, over fiber or high-quality copper, the error rate is much lower, so error detection and retransmission is usually more efficient there for dealing with the occasional error.

three different error-detecting codes:
1. parity.
2. checksums.
3. cyclic redundancy checks (crcs).

the first error-detecting code, in which a single parity bit is appended to the data. the parity bit is chosen so that the number of 1 bit in the codeword is even (or odd). doing this is equivalent to computing the (even) parity bit as the modulo 2 sum or xor of the data bits. for example, when 1011010 is sent in even parity, a bit is added to the end to make it 10110100. with odd parity 1011010 becomes 10110101. a code with a single parity bit has a distance of 2, since any single-bit error produces a codeword with the wrong parity. this means that it can detect single-bit errors.

the second kind of error-detecting code, the checksum, is closely related to groups of parity bits. the word ‘‘checksum’’ is often used to mean a group of check bits associated with a message, regardless of how are calculated. a group of parity bits is one example of a checksum. however, there are other, stronger checksums based on a running sum of the data bits of the message. the checksum is usually placed at the end of the message, as the complement of the sum function. this way, errors may be detected by summing the entire received codeword, both data bits and checksum. if the result comes out to be zero, no error has been detected.

a third and stronger kind of error-detecting code is in widespread use at the link layer: the crc (cyclic redundancy check), also known as a polynomial code. polynomial codes are based upon treating bit strings as representations of polynomials with coefficients of 0 and 1 only. a k-bit frame is regarded as the coefficient list for a polynomial with k terms, ranging from xk–1 to x0. such a polynomial is said to be of degree k?1. the high-order (leftmost) bit is the coefficient of xk?1, the next bit is the coefficient of xk?2, and so on. for example, 110001 has 6 bits and thus represents a six-term polynomial with coefficients 1, 1, 0, 0, 0, and 1: 1x5 + 1x4 + 0x3 + 0x2 + 0x1 + 1x0. polynomial arithmetic is done modulo 2, according to the rules of algebraic field theory. it does not have carries for addition or borrows for subtraction. both addition and subtraction are identical to exclusive or.
for example:
10011011 00110011 11110000 01010101
+ 11001010 + 11001101 ? 10100110 ? 10101111
- -
01010001 11111110 01010110 11111010

long division is carried out in exactly the same way as it is in binary except that the subtraction is again done modulo 2. a divisor is said ‘‘to go into’’ a dividend if the dividend has as many bits as the divisor.

when the polynomial code method is employed, the sender and receiver must agree upon a generator polynomial, g(x), in advance. both the high- and loworder bits of the generator must be 1. to compute the crc for some frame with m bits corresponding to the polynomial m(x), the frame must be longer than the generator polynomial. the idea is to append a crc to the end of the frame in such a way that the polynomial represented by the checksummed frame is divisible by g(x). when the receiver gets the checksummed frame, it tries dividing it by g(x). if there is a remainder, there has been a transmission error.

the algorithm for computing the crc is as follows:
1. let r be the degree of g(x). append r zero bits to the low-order end of the frame so it now contains m + r bits and corresponds to the polynomial xrm(x).
2. divide the bit string corresponding to g(x) into the bit string corresponding to xrm(x), using modulo 2 division.
3. subtract the remainder (which is always r or fewer bits) from the bit string corresponding to xrm(x) using modulo 2 subtraction. the result is the check summed frame to be transmitted. call its polynomial t(x).

figure below illustrates the calculation for a frame 1101011111 using the generator g(x)= x4+x+1. it should be clear that t(x) is divisible (modulo 2) by g(x). in any division problem, if you diminish the dividend by the remainder, what is left over is divisible by the divisor. for example, in base 10, if you divide 210,278 by 10,941, the remainder is 2399. if you then subtract 2399 from 210,278, what is left over (207,879) is divisible by 10,941.

if a transmission error occurs, so that instead of the bit string for t(x) arriving, t(x) + e(x) arrives. each 1 bit in e(x) corresponds to a bit that has been inverted. if there are k 1 bits in e(x), k single-bit errors have occurred. a single burst error is characterized by an initial 1, a mixture of 0s and 1s, and a final 1, with all other bits being 0. upon receiving the checksummed frame, the receiver divides it by g(x) that is, it computes [t(x) + e(x)]/g(x). t(x)/g(x) is 0, so the result of the computation is simply e(x)/g(x). those errors that happen to correspond to polynomials containing g(x) as a factor will slip by all other errors will be caught.