NOTES ON

COMPUTER NETWORKS

Organized & Prepared By

Sharafat Ibn Mollah Mosharraf
12th Batch (05-06)
Dept. of Computer Science & Engineering
University of Dhaka

TABLE OF CONTENTSNETWORK MODELS: OSI & TCP/IP – BASIC IDEA ......................................................................................................................... 1
TASKS OF THE LAYERS AT A GLANCE ........................................................................................................................................... 5
CHAPTER 3: TRANSPORT LAYER .................................................................................................................................................. 7
CHAPTER 4: NETWORK LAYER................................................................................................................................................... 18
CHAPTER 5: LINK LAYER ............................................................................................................................................................ 42

NETWORK MODELS: OSI & TCP/IP – BASIC IDEA
What is this Data Communication or Networking course all about?
We want to transfer data between two computers. How can we do it? That’s the question we’ll try to findan answer for in the Data Communication or Networking courses – how to communicate among computers.

Designing the solution
So, how would we start? Let’s try to visualize the situation. Suppose, you’re using Yahoo Messenger.
You want to say “hello” to your friend who also is using Yahoo Messenger. Then, how would you send thisdata (i.e., the text “hello”)? Also, how would your friend receive that data?

The Application Layer
You’re using Yahoo Messenger, which is an application, or, in other words, a running process.
Similarly, your friend is also running the Messenger process in his computer. If we think in the simplest
way, we can find that it’s sufficient for the process from your end to just send the data, and similarly, it’ssufficient for the process from his end to just receive the data – nobody needs to know how the data is
traveling in-between.
So, the application just needs to prepare the data to be sent, or, prepare itself for receiving data. This is
the first step of data transfer, which is known as the task of application layer.
Yahoo Messenger

hello

hello

Intermediate
Network

LAN Card

LAN Card

Transmits
Data

Your
ComputerYahoo Messenger

Receives
DataYour friend’s
ComputerFigure 1: Application Layer Communication.

The Transport Layer
In the application layer, we didn’t pay attention to one aspect. Problem arises when we consider the factthat several processes run simultaneously in a computer, but there is only a single device (e.g., LAN card)
which receives or transmits data. How would your friend’s LAN card know which process that data is to be
forwarded to? This situation is depicted in figure 2.1 below.
Yahoo Messenger

hello

hello

LAN Card
Your
ComputerTransmits
Data

Intermediate
Network

LAN Card???
Where
should thisdata beforwarded?

Receives
Data

Yahoo Messenger
Firefox
MS WordYour friend’s
ComputerFigure 2.1: Problem with data transfer when there are multiple processes.

The solution? Well, we can send an extra info with the data which may contain something that would
identify the destination process. Then the LAN card would know to which process that data is to be
forwarded.

1

Now, what’s that “something” that would identify the process? The name of the process? Well, there
might be running several instances of the same program – all of whom have the same name. In that case, it’dsill be impossible to uniquely identify a process which would receive the data.
Well, how about process IDs? They’re unique, of course. But the problem is, they’re not fixed for eachprocess. Suppose, right at this moment, your Yahoo Messenger has the PID 3483. When you’d restart the
program, the PID may become 3521. So, how would the sending process in your computer know beforehand
the PID of the receiving process in your friend’s computer?
We need to come up with something else. And that something else is what we call “ports”. You knowwhat the term port means – a place (seaport or airport) where people and merchandise can enter or leave acountry. Similarly, each program is assigned a fixed port number through which a data can enter to of leavefrom that program. No matter what the PID of a process is, it would bind itself to a fixed port number whichmust be known to the data sending process. Also, when a process binds itself to a particular port, no otherprocess can bind itself to that port.
Now we get the idea. We shall send the destination port number along with the data, so that it can bereceived by the right process. We call this extra information a “header”. This is the second layer of the datatransfer process, which is called the transport layer.
Yahoo Messenger
5555

hello

Application Layer

hello

Transport Layer

5555

Intermediate
Network

LAN Card

Your
Computer

1. Extract Port
number from header

Transmits
Data

Port 5555: Messenger
2. Send data toprocess bound toport 5555

hello

LAN Card

Port 3218: Firefox
MS WordYour friend’s
Computer

Receives
Data

Figure 2.2: Data communication up to transport layer.

The Network Layer
Unfortunately, we forgot another fact. It’s obvious that more than one computers may be running Yahoo
Messenger. Then how it can be decided that which computer should receive the data? This situation isdepicted in figure 3.1 below.
Yahoo Messenger
5555

hello

Application Layer

Port 5555: Messenger

helloTransport Layer

Port 3218: Firefox
5555

Your
Computer

LAN Card

Intermediate
Network

hello

LAN Card???
To whichcomputershould thisdata beforwarded?

Transmits
Data

MS WordYour friend’s
Computer
Port 5555: Messenger

LAN Card
Your some otherfriend’s Computer
Figure 3.1: Problem with data transfer when there are multiple computers connected together in a network.

The solution is obvious. We’ll assign each computer a fixed and unique ID, which is called a Network
Address or IP Address, and add another header to the data packet which will contain the destination IP
address. The layer in which this task is performed is called the network layer. Note that later, we’ll study indetails how the data will automatically reach the intended computer from the network.

2

Yahoo Messenger

hello

Application Layer

5555

hello

Transport Layer

172.16.8.2 5555

hello

Network Layer

172.16.8.1
LAN Card

Intermediate
Network

Transmits
Data

hello

Port 5555: Messenger

5555

hello

Port 3218: Firefox

172.16.8.2 5555

hello

LAN Card

MS Word172.16.8.2

Receives
Data
Port 5555: Messenger

LAN Card
172.16.8.3
Figure 3.2: Data communication up to network layer.

The Data Link Layer
So far, we were concerned with just sending and receiving data only. Now it’s time to examine theintermediate network.
Suppose you’re in Bangladesh and your friend is in USA. Then how would your data travel such a long
distance? There is no point mentioning the obvious fact that you cannot connect your computer to yourfriend’s computer with cable directly. There must be some intermediate devices (called hops or nodes)
which would carry on (or keep forwarding) your data until it reaches its destination. So, merely mentioning
the IP address of the destination computer wouldn’t help. You must send your data to your near-most hop,and it would relay it to his near-most hop (which is towards the destination computer, not on the opposite
direction of it). Therefore, you’d need to know the address of your near-most hop. However, this address is
not the IP address; this is called Hardware Address or MAC (Machine Address Code) Address. (Why adifferent identification system is used here will be explained shortly.)
This hardware address is added to the data as another header in the layer called the data link layer.
However, a trailer is also added in this layer, which contains CRC (Cyclic Redundancy Check) code forverifying the integrity of the packet.
The hop receiving the data packet would change the header by putting the hardware address of its nearmost hop’s hardware address and pass the packet on. This process continues until the packet reaches thedestination computer (called the host). The process is depicted in figure 4.

The Physical Layer
We’ve logically designed everything appropriately. But there remains the last question – how would thedata actually move from hop-to-hop? Would it be transmitted single-bit at a time or multiple-bits at a time?
Would it travel through a piece of wire or through wind (or, in other words, wireless)? Which transmission
medium or transmission scheme would be more efficient or more reliable? These questions are answered in
the physical layer. The physical layer is responsible for movements of individual bits from one hop (node) tothe next.
Well, this concludes the network model we were trying to discover. This model is called the TCP/IP
Model. Although we’ve observed that the TCP/IP model has five layers, actually, it has four layers. The datalink layer and the physical layer are counted as a single layer.

3Source Computer
IP: 172.16.8.1 || MAC: 4E3209FA

hello

Application Layer

5555

hello

Transport Layer

172.16.8.2 5555

hello

Network Layer

39FB88CD 172.16.8.2 5555

helloIntermediate Hop 1
MAC: 39FB88CD

CRC

Data Link Layer

After header
modification

88273CB3 172.16.8.2 5555

hello

CRC

Physical Layer

Transmits Data

Destination Computer
IP: 172.16.8.2 || MAC: 1003CD45

Intermediate Hop 2

hello

MAC: 88273CB3
5555

hello

172.16.8.2 5555

hello

1003CD45 172.16.8.2 5555

hello

After header
modification

1003CD45 172.16.8.2 5555

CRC

hello

CRC

Receives Data

Figure 4: Complete Network Model for transferring data from one computer to another.

Next comes the OSI (Open Systems Interconnection) Model, which is the same as the TCP/IP model
except that it splits the application layer into two more layers – one is called the presentation layer, and theother is called the session layer.
[Omitted due to lack of time…]

4

TASKS OF THE LAYERS AT A GLANCE
Tasks of Application layer:
How the receiver should interpret the incoming data.
Generally, we use application layer header fields to indicate the nature of the data contained in thepacket. For example, in a field named ‘error’, we can set 1 to indicate that this is a packet containing error
information.
Tasks of Presentation layer:
Concerned with the representation of data.
1. Translation: Converting system dependent data format into system independent data format andvice-versa.
2. Encryption
3. Compression
Tasks of Session layer:
1. Dialog Control: Half-duplex, full-duplex
2. Synchronization: Inserting a checkpoint after a certain amount of data so that when some data getlost or corrupted, only that amount of data may be resent instead of resending the whole message.
Tasks of Transport layer:
Responsible for process-to-process delivery of message.
1. Port / Service-point Addressing
2. Providing Reliability
a. Packet loss
i. General reliable data transfer protocol (sending and receiving acknowledgement)
ii. Pipelined reliable data transfer protocol
1. GBN (Go-Back-N)
2. SR (Selective Repeat)b. Packet corruption: Checksum
3. Flow Control: Use a window.
4. Congestion Control
From reliability point of view, transport layer has the following tasks:
5. Segmentation and Reassembly: So that when a segment gets lost or corrupted, only that segment
may be resent instead of resending the whole message.
6. Connection Control: TCP (connection-oriented) [provides reliability of packet loss], UDP(connectionless) [if no packet-loss reliability is needed]. [However, both must provide reliability of
packet corruption.]
Tasks of Network layer:
Responsible for host-to-host delivery of message.
1. Logical Addressing
2. Routing: Deciding through which path a datagram should go from source to destination.
Tasks of Link Layer:
Responsible for hop-to-hop / node-to-node delivery of message.
1. Physical / MAC Addressing
2. Reliability
a. Packet loss : GBN, SR (mainly used for wireless communication)b. Packet corruption: CRC
3. Flow Control (adapter buffer may overflow): Ethernet sends a PAUSE frame
4. Multiple access control (multiple nodes send frames simultaneously through a single channel. How
the receiver would distinguish among the frames?)5

From reliability point of view, link layer has the following task:
5. Framing: So that when a frame gets lost or corrupted, only that segment may be resent instead ofresending the whole message.
Tasks of Physical Layer:
1. Representation / Encoding of Bits: How 0’s and 1’s are changed into signals.
2. Data / Transmission Rate. For example, Ethernet has a rate of 10/100/1000 Mbps.
3. Physical Topology: Star, Bus, Ring, Mesh, Hybrid topologies.

6

CHAPTER 3
TRANSPORT LAYER
Concepts
3.1

TCP and UDP Segment Structures

3.2

UDP Checksum (a.k.a. Internet Checksum)
1. Add all the 16-bit words in the UDP segment.
2. If the addition has overflow, then wrap it around.
3. The checksum is the 1’s complement of the final sum.

3.3

Building a reliable data transfer protocol
1. Reliable data transfer over a perfectly reliable channel (rdt 1.0)
 Just send and receive packets
2. Reliable data transfer over a channel with bit errors (rdt 2.0)
 Use retransmission (ARQ / Stop-and-wait protocol).
 How? – By feedbacking ACK and NACK.
 Problem: The ACK/NACK itself could be corrupted.
Solutions:
1. Add enough checksum bits to allow the not only to detect, but also to recover from bit
errors.
2. Resend the current data packet.
Problem with the 2nd solution: Receiver will receive duplicate packets.
Solution to this new problem: Put a sequence number (0 or 1) in each packet. (rdt 2.1)
 Instead of sending a NACK, we can resend the ACK of the last received non-corrupt packet.
(rdt 2.2)
3. Reliable data transfer over a Lossy channel with bit errors (rdt 3.0)
 Retransmit after timeout.
 Timeout interval? – Should be at least as long as a round-trip delay between sender andreceiver.
7

3.4

 Problem: Performance is poor.
Solution: Use pipelining for sending packets.
Consequences of this solution:
1. Range of sequence numbers must be increased.
2. Sender and receiver may have to buffer packets (which are sent/received, but not yet
acknowledged).
3. The above two depends on the manner in which a data transfer protocol responds to lost,
corrupted and overly delayed packets.
Approaches toward pipelined error recovery:
1. Go-Back-N (GBN) [Sliding Window Protocol]
 Sender can transmit multiple packets without waiting for an acknowledgement.
 But sender is constrained to have no more than some maximum allowable number, N, of
unacknowledged packets in the pipeline.
 An acknowledgement for packet with sequence number n will be taken to be a cumulative
acknowledgement, indicating that all packets with a sequence number up to and including nhave been correctly received at the receiver.
 Range of sequence numbers: [0, 2k – 1], where k = Number of bits in the packet sequencenumber field.
 Sender’s view of sequence numbers in GBN:
base

0

1

2

3

4

nextseqnum

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

Window Size N
Keys:
Already ACK’d [0, base – 1]

Sent, not yet ACK’d [base, nextseqnum - 1]

Usable, not yet sent [nextseqnum, base + N - 1]

Not usable [>= base + N]

 Problem with GBN:
Poor performance when window size and bandwidth-delay product are both large. In that case,many packets can be in the pipeline. A single packet error can thus cause GBN to retransmit alarge number of packets, many unnecessarily.
2. Selective Repeat (SR) Avoids unnecessary retransmissions by having the sender retransmit only those packets that it
suspects were received in error at the receiver.
 Acknowledge each correctly received packet whether or not it is in order.
 Out-of-order packets are buffered until any missing packets are received, at which point a batchof packets can be delivered in order to the upper layer.
 The receiver must re-acknowledge already received packets with certain sequence numbers
below the current window base.
 Problem with SR:
Lack of synchronization between sender and receiver windows has important consequences:
how can the receiver tell whether a received packet is of the current sequence number, or of analready ACK’ed sequence number?
Solution:Set the window size to less than or equal to half the size of the sequence number space for SR
protocols.
8

3.5

Maximum Segment Size (MSS) of a TCP Packet
 The maximum amount of data that can be grabbed and placed in a segment is limited by the
MSS (maximum segment size).
 The MSS is typically set by first determining the length of the largest link-layer frame that canbe sent by the local sending host (the so-called MTU – maximum transmission unit), and thensetting the MSS to ensure that a TCP segment (when encapsulated in an IP datagram) will fit
into a single link-layer frame. Common values for the MTU are 1,460 bytes, 536 bytes, and512 bytes.
 The MSS is the maximum amount of application-layer data in the segment, not the maximum
size of the TCP segment including headers.

3.6

Sequence Numbers and Acknowledgement Numbers
 Sequence numbers are over the stream of transmitted bytes and not over the series oftransmitted segments. The sequence number for a segment is therefore the bytes-stream
number of the first byte in the segment.
 Both sides of a TCP connection randomly choose an initial sequence number. This is done tominimize the possibility that a segment that is still present in the network from an earlier,already-terminated connection between two hosts is mistaken for a valid segment in a laterconnection between the same two hosts (which also happen to be using the same port numbers
as the old connection).
 The acknowledgement number that the receiver puts in its segment is the sequence number ofthe next byte the receiver is expecting from the sender.
 TCP provides cumulative acknowledgement as it only acknowledges bytes up to the firstmissing byte in the stream.
 What does a host do when it receives out-of-order packets?
TCP RFCs do not impose any rules here. Possible solutions:
1. The receiver immediately discards those segments.
2. The receiver keeps those segments into the buffer.
The latter choice is more efficient in terms of network bandwidth, and is the approach taken inpractice.

3.7

Round-Trip Time Estimation and Timeout
EstimatedRTT = (1 – α) × EstimatedRTT + α × SampleRTT
DevRTT = (1 – β) × DevRTT + β × | SampleRTT – EstimatedRTT |TimeoutInterval = EstimatedRTT + 4 × DevRTT

3.8

TCP’s Reliable Data Transfer Mechanism
Consider what happens when the sender sends a sequence of segments 1, 2, … N, and all of thesegments arrive in order without error at the receiver. Further suppose that the acknowledgement for
packet n < N gets lost, but the remaining N – 1 acknowledgements arrive at the sender before theirrespective timeouts. TCP would retransmit at most, one segment, namely, segment n. Moreover, TCP
would not even retransmit segment n if the acknowledgement for segment n + 1 arrived before thetimeout for segment n.
TCP’s error recovery mechanism is probably best categorized as a hybrid of GBN and SR
protocols.

9TCP ACK generation:
Event

TCP Receiver Action

Arrival of in-order segment with expected sequence Delayed ACK. Wait up to 500 msec for arrival of
number. All data up to expected sequence number another in-order segment. If next in-order segment
already acknowledged.
does not arrive in this interval, send an ACK.
Arrival of in-order segment with expected sequence Immediately send single cumulative ACK, ACKing
number. One other in-order segment waiting for both in-order segments.
ACK transmission.
Arrival of out-of-order segment with higher-than- Immediately send duplicate ACK, indicating
expected sequence number. Gap detected.
sequence number of next expected byte (which is thelower end of the gap).
Arrival of segment that partially or completely fills in Immediately send ACK, provided that segment starts
gap in received data.
at the lower end of gap.

3.9

Doubling the Timeout Interval
Whenever the timeout event occurs, TCP retransmits the not yet acknowledged segment with thesmallest sequence number. But each time TCP retransmits, it sets the next timeout interval to twice theprevious value, rather than deriving it from the last EstimatedRTT and DevRTT.
However, whenever the timer is started after either of the two other events (i.e., data received
from application above, and ACK received), the TimeoutInterval is derived from the most recent
values of EstimatedRTT and DevRTT.
This modification provides a limited form of congestion control.

3.10 Fast Retransmit
If the TCP sender receives three duplicate ACKs for the same data, it takes this as an indicationthat the segment following the segment that has been ACKed three times has been lost. In that case,
the TCP sender performs a fast retransmit – retransmitting the missing segment before that segment’s
timer expires.
3.11 Flow Control
Because TCP is not permitted to overflow the allocated buffer, we must have
LastByteRcvd – LastByteRead ≤ RcvBuffer

The receive window, denoted RcvWindow, is set to the amount of spare room in the buffer:
RcvWindow = RcvBuffer – [LastByteRcvd – LastByteRead]

The TCP specification requires the sender to continue to send segments with one data byte when
the receiver’s receive window is zero.
3.12 TCP Connection Management103.13 Principles of Congestion Control
The Causes and the Costs of Congestion
1. Scenario 1: Two senders, a Router with Infinite Buffers
Two hosts (A and B) each have a connection that shares a single hop between source anddestination.
 Assume:
 λin bytes/sec = The average rate Host A is sending original data into the connection.
Original means each unit of data is sent into the socket only once.
 Data is encapsulated and sent – no error recovery (e.g., retransmission), flow control orcongestion control is performed.
 Host B operates in a similar manner and it too is sending at a rate of λin bytes/sec.
 Outgoing link capacity of router = R. The link is shared.
 The router has an infinite amount of buffer space.

 Performance of Host A’s connection under this first scenario:
 Per-Connection Throughput (number of bytes/sec at the receiver): Sending rate between 0 and R/2: Throughput = Sender’s sending rate Sending rate above R/2: Throughput = R/2
Reason: The link simply can’t deliver packets to receiver at a steady-state rate thatexceeds R/2.
11

 Achieving a per-connection throughput of R/2 might actually appear to be a good thing,because the link is fully utilized in delivering packets to their destinations. However,operating near link capacity consequences in larger delay.

 Average Delay: As the sending rate approaches R/2, the average delay becomes larger and larger.
 When the sending rate exceeds R/2, the average number of queued packets in the routeris unbounded, and the average delay between source and destination becomes infinite.
 Cause of congestion as learnt from this scenario:
Operating at an aggregate throughput of near or above R.
 Cost of congestion as learnt from this scenario:
Large queuing delays are experienced.
2. Scenario 2: Two senders, a Router with Finite Buffers
 Assume:
 The router has an infinite amount of buffer space.
Consequence: Packets will be dropped when arriving to an already-full buffer.
 Each connection is reliable – retransmission on packet loss is performed.
 λin bytes/sec = The average rate Host A is sending original data into the connection.
 λ′in bytes/sec = The offered load to the network (original + retransmitted data) Performance
Depends on how retransmission is performed.
1. Sender is able to somehow determine whether or not a buffer is free in the router andthus sends a packet only when a buffer is free.
 No loss would occur: λin = λ′in.
 Throughput = λin From a throughput standpoint, performance is ideal – everything that is sent is received.
 Note that the average host sending rate cannot exceed R/2 under this situation, since
packet loss is assumed never to occur.
2. Sender retransmits only when a packet is known for certain to be lost.
Let, λ′in = R/2.
Let, at this value of offered load, throughput = R/3.
∴ The rate of actual data = throughput = R/3∴ The rate of retransmitted data = R/2 – R/3 = R/6
 Cost of congestion as learnt from this scenario:
The sender must perform retransmissions in order to compensate for dropped (lost)12

packets due to buffer overflow.

3. The sender may time out prematurely and retransmit a packet that has been delayedin the queue but not yet lost.
In this case, the work done by the router in forwarding the retransmitted copy of theoriginal packet was wasted, as the receiver will have already received the original copy ofthis packet. The router would have better used the link transmission capacity to send a
different packet instead.
 Throughput: R/4
Reason: Since each packet is forwarded twice (on average), the throughput will havean asymptotic value of R/4 as the offered load approach R/2.
 Cost of congestion as learnt from this scenario:
Unneeded retransmissions by the sender in the face of large delays may cause arouter to use its link bandwidth to forward unneeded copies of a packet.
3. Scenario 3: Four Senders, Routers with Finite Buffers, and Multi-hop Paths
Four hosts transmit packets, each over overlapping two-hop paths.
 Assume:
 Each host uses a time-out/retransmission mechanism to implement reliable data transfer
service.
 All hosts have the same value of λin.
 All router links have capacity R bytes/sec.
 The A-C connection shares router R1 with D-B connection, and R2 with B-D connection.

13

 For extremely small values of λin,
 Buffer overflows are rare.
 The throughput approximately equals the offered load.
 For slightly larger values of λin,
 The corresponding throughput is also larger, since more original data is being transmitted
into the network and delivered to the destination, and overflows are still rare.
 Thus, for small values of λin, an increase in λin results in an increase in λout.
 For extremely large values of λin (and hence λ′in), Consider the router R2.
 The A-C traffic arriving from router R1 to R2 can have an arrival rate at R2 that is at mostR, the capacity of the link from R1 to R2, regardless of the value of λin.
 The arrival rate of B-D traffic at R2 can be much larger than that of the A-C traffic.
 Because the A-C and B-D traffic must compete at router R2 for the limited amount of
buffer space, the amount of A-C traffic that successfully gets through R2 (i.e., is not lost
due to buffer overflow) becomes smaller and smaller as the offered load from B-D getslarger and larger.
 In the limit, as the offered load approaches infinity, an empty buffer at R2 is immediately
filled by a B-D packet, and the throughput of the A-C connection at R2 goes to zero in thelimit of heavy traffic.
 Cost of congestion as learnt from this scenario:
When a packet is dropped along a path, the transmission capacity that was used at each of
the upstream links to forward that packet to the point at which it is dropped ends up having
been wasted.
3.14 Approaches to Congestion Control
Congestion control approaches can be distinguished based on the whether or not the network layer
provides any explicit assistance to the transport layer for congestion control purposes:
1. End-to-End Congestion Control
 The network layer provides no explicit support to the transport layer for congestion control
purposes.
 Even the presence of congestion in the network must be inferred by the end systems based
only on observed network behavior (e.g., packet loss and delay).
 Implemented by TCP.
2. Network-Assisted Congestion Control
 Network-layer components (i.e., routers) provide explicit feedback to the sender regarding
the congestion state in the network.
 Implemented by ATM [the ATM ABR (Available Bit-Rate) congestion control mechanism].
3.15 TCP Congestion Control
The approach taken by TCP is to have each sender limit the rate at which it sends traffic into its
connection as a function of perceived network congestion. If little congestion is perceived, the send
rate is increased; if much congestion is perceived, the send rate is decreased.
But this approach raises three questions: How does a TCP sender limit the rate at which it sends traffic into its connection?
Introduce a congestion window, which imposes a constraint on the rate of transmission.
Specifically, the amount of unacknowledged data at a sender may not exceed the minimum ofcongestion window and receive window. That is:
LastByteSent – LastByteAcked ≤ min(CongWin, RcvWindow)
14

Ignoring the RcvWindow constraint, roughly, at the beginning of every RTT, theconstraint CongWin permits the sender to send CongWin bytes of data into the connection; andat the end of the RTT, the sender receives the acknowledgements for the data.
Thus, The sender’s send rate is roughly CongWin/RTT bytes/sec. By adjusting the valueof CongWin, the sender can therefore adjust the rate at which it sends data into its connection.
 How does a TCP sender perceive that there is congestion on the path between itself andthe destination?
 How congestion is detected
When there is excessive congestion, then one (or more) router buffers along the path
overflows, causing a datagram to be dropped. The dropped datagram, in turn, results in aloss event at the sender – either a timeout or the receipt of three duplicate ACKs – which istaken by the sender to be an indication of congestion on the sender-to-receiver path.
 How congestion-freeness is detected
In this case, acknowledgements for previously unacknowledged segments will bereceived at the TCP sender. TCP will take the arrival of these acknowledgements toincrease its congestion window size (and hence its transmission rate).
 What algorithm should the sender use to change its send rate as a function of perceived
end-to-end congestion?
It’s called TCP congestion control algorithm.
3.16 TCP Congestion Control Algorithm
The algorithm has three major components:
1. Additive-Increase, Multiplicative Decrease (AIMD)
2. Slow Start (SS)
3. Reaction to Timeout Events
Additive-Increase, Multiplicative Decrease (AIMD) Approach: Increase transmission rate (window size), probing for usable bandwidth, until loss
occurs.
 Additive Increase: Increase CongWin by 1 MSS every RTT until loss detected.
 This can be accomplished in several ways; a common approach is for the TCP sender toincrease its CongWin by MSS (MSS/CongWin) bytes whenever a new acknowledgement
arrives.
For example, if
MSS = 1,460 bytes
CongWin = 14,600 bytes∴ No. of segments sent within an RTT = 10
Each arriving ACK increases the congestion window size by 1/10 MSS.
∴ After acknowledgements for all 10 segments have been received, the value of
CongWin will have increased by MSS, as desired.
 This linear increase phase is known as congestion avoidance (CA).
 Multiplicative Decrease: Cut CongWin in half after loss. However, CongWin is not allowed todrop below 1 MSS.
Slow Start (SS) When a TCP connection begins, the value of CongWin is typically initialized to 1 MSS.
 Instead of increasing its rate linearly during this initial phase, a TCP sender continues toincrease its rate exponentially by doubling its value of CongWin every RTT until there is a loss
event, at which time CongWin is cut in half and then grows linearly, as described above.
15

Reaction to Loss Events
 Timeout Events
 TCP sender enters a slow-start phase – i.e., sets the congestion window to 1 MSS and thengrows the window exponentially. The window continues to grow exponentially until
CongWin reaches one half of the value it had before the timeout event. At that point,
CongWin grows linearly.
 TCP manages these more complex dynamics by maintaining a variable called Threshold,which determines the window size at which slow start will end and congestion avoidance
will begin. The variable is initially set to a large value (65 Kbytes in practice) so that it has
no initial effect. Whenever a loss event occurs, the value of Threshold is set to one half ofthe current value of CongWin.
 Thus, while in SS, a TCP sender increases the value of CongWin exponentially fast until
CongWin reaches Threshold. When CongWin reaches Threshold, TCP enters the CA phase,during which CongWin ramps up linearly as described earlier.
 Both TCP Tahoe and TCP Reno acts in this way.
 Triple Duplicate ACKs TCP Tahoe – behaves as described in the timeout event – enters an SS phase.
 TCP Reno – the congestion window is cut in half and then increases linearly.
 Reason: Even though a packet has been lost, the arrival of three duplicate ACKs
indicates that some segments have been received at the sender. Thus, unlike the case ofa timeout, the network is showing itself to be capable of delivering at least somesegments, even if other segments are being lost to congestion.
 This canceling of the SS phase after a triple duplicate ACK is called fast recovery.

Figure: TCP Reno’s Reaction to loss events.
16

3.17 TCP Throughput
 Ignore the SS phases, as they are typically very short (since the sender grows out of the phase
exponentially fast).
 Let,
Current window size = w bytes
Current round-trip time = RTT sec∴ Transmission rate = w/RTT (roughly)
Let, W be the value of w when a loss event occurs.
Assuming that RTT and W are approximately constant over the duration of the connection, the
TCP transmission rate ranges from 
to
.






Because TCP’s throughput increases linearly between the two extreme values, we haveAverage throughput of connection =  

17



/

=






=

.

CHAPTER 4NETWORK LAYER
4.1

Routing and Forwarding
Routing refers to the network-wide
process that determines the end-to-end paths
that packets take from source to destination.
Forwarding refers to the router-local
action of transferring a packet from an input
link interface to the appropriate output linkinterface.
How forwarding works
Every router has a forwarding table. A
router forwards a packet by examining thevalue of a field in the arriving packet’s
header, and then using this value to index
into the router’s forwarding table. The result
from the forwarding table indicates to whichof the router’s link interfaces the packet is tobe forwarded.
How forwarding tables are configured?
Using routing algorithms. Coming soon…

4.2

4.3

Network Service Model
Network
Architecture

ServiceModel

Bandwidth
Guarantee

No-Loss
Guarantee

Ordering

TimingCongestion
ControlInternet

Best Effort

None

None

Not
Maintained

None

ATM
(AsynchronousTransfer Mode)

ABR(Available
Bit Rate)

Guaranteed
Minimum

None

Any
Order
In OrderNot
MaintainedCongestion
Indication
Provided

CBR(Constant
Bit Rate)

Guaranteed
Constant
Rate

Yes

In OrderMaintainedCongestion Will
Not Occur

Virtual Circuit (VC) Networks
A VC consists of
1. A path (i.e., a series of links and routers) between the source and destination hosts
2. VC numbers, one number for each link along the path
3. Entries in the forwarding table in each router along the path.
A packet belonging to a VC will carry a VC nunber in its header. Because a VC may have a
different VC number on each link, each intervening router must replace the VC number of eachtraversing paket with a new one. The new VC number is obtained from the forwarding table.
In a VC network, the network’s routers must maintain connection state information for theongoing connections. Specifically, each time a new connection is established across a router, a newconnection entry must be added to the router’s forwarding table; and each time a connection isreleased, an entry must be removed from the table.
18

Example of forwarding in a VC network
Incoming Interface Incoming VC#
1
12
2
63
3
7
1
97
…
…

Outgoing Interface Outgoing VC#
2
22
1
18
2
17
3
87
…
…

Why doesn’t a packet just keep the same VC number on each of the links along its route?
1. Replacing the number from link to link reduces the length of the VC number field in packet
header.
2. VC setup is simplified. Specifically, with multiple VC numbers, each link in the path canchoose a VC number independently of the VC number chosen at other links along the path. If a
common VC number were required for all links aong the path, the routers would have to
exchange and process a substantial number of messages to agree on a common VC number tobe used for connection.
Phases in VC
1. VC Setup Sending transport layer contacts the network layer, specifies the receiver’s address, andwaits for the network to set up the VC.
 Network layer- determines the path between sender and receiver, and the VC number for eachlink along the path.
- adds an entry in the forwarding table in each router along the path.
- may also reserve resources (e.g. bandwidth) along the path of the VC.
2. Data Transfer
3. VC Teardown
 Sender (or receiver) informs the network layer of its desire to terminate the VC.
 Network layer- informs the end system on the other side of the network of the call termination.
- updates the forwarding tables in each of the routers on the path to indicate that
the VC no longer exists.

19

Signaling Messages and Protocols
The messages that the end systems send into the network to initiate or terminate a VC, and themessages pased between the routers to set up the VC are known as signaling messages, and theprotocols used to exchange these messages are often referred to as signaling protocols.
4.4

Datagram Networks
In a datagram network, each time an end system wants to send a packet, it stamps the packet withthe address of the destination end system and then pops the packet into the network. This is done
without any VC setup. Routers in a datagram network do not maintain any state information about
VCs.
A packet passes through a series of routers. When a packet arrives at the router, the router uses thepacket’s destination address to lookup the appropriate output link interface in the forwarding table. Itthen forwards the packet to that output link interface.
For example, a router with 4 links may have the following forwarding table:
Destination Address Range

Link Interface

11001000 00010111 00010000 00000000
through
11001000 00010111 00010111 11111111

011001000 00010111 00011000 00000000
through
11001000 00010111 00011000 11111111

1

11001000 00010111 00011001 00000000
through
11001000 00010111 00011111 11111111

2otherwise3

Problem: There have to be 232 (≈ 4 billion) entries in each router’s forwarding table!
Solution: Use Longest Prefix Matching.
When there are multiple matches, the router uses the longest prefix matching rule; that is, it finds
the longest matching entry in the table and forwards the packet to the link interface associated with thelongest prefix match. The table might look like the following:
Prefix Match
Link Interface
11001000 00010111 00010
011001000 00010111 00011000
1
11001000 00010111 00011
2
otherwise3

As an example, the destination address 11001000 00010111 00011000 1010101 is mapped to thelink interface 1.
Although routers in datagram networks maintain no connection state information, they
nevertheless maintain forwarding state information in their forwarding tables. Because forwarding
tables in datagram networks can be modified at any time, a series of packets sent from one end system
to another may follow different paths through the network and may arrive out of order.

20

4.5

Inside the Router
High-Level View of a Generic Router Architecture
There are four components of a router:
1. Input Ports Physical layer functions: terminating an incoming physical link to a router.
 Data link layer functions: protocol, decapsulation.
 Lookup and forwarding function:- Data packets are forwarded into the switching fabric of the router to place at theappropriate outupt port.
- Control packets (e.g., packets carrying routing protocol information) areforwarded from input port to the routing processor.
2. Switching FabricConnects the router’s input ports to its output ports.
3. Output Ports
 Stores the packets that have been forwarded to it through the switching fabric and thentransmits the packets on the outgoing link.
 The output port thus performs the reverse data link and physical layer functionalities of
the input port.
4. Routing Processor
 Executes routing protocols
 Maintains the routing information and forwarding tables
 Performs network management functions within the router21

Switching Techniques
1. Switching via memory
 An input port with an arriving packet signals the routing processor via an interrupt.
 The packet is then copied from the port into memory.
 The routing processor then extracts the destination address from the header, looks up
the appropriate output port in the forwarding table, and copies the packet to the output
port buffers.
2. Switching via a bus
 The input ports transfer a packet directly to the output port over a shared bus, without
the intervention by the routing processor.
 As the bus is shared, only one packet at a time can be transferred over the bus. Thus, thebandwidth of the router is limited to the bus speed.
3. Switching via an interconnection network / crossbar switch
 A crossbar switch is an interconnection netgwork consisting of 2n buses that connect n
input ports to n output ports.
 A packet arriving at an input port travels along the horizontal bus attached to the input
port until it intersects with the vertical bus leading to the desired output port.
 If the vertical bus is being used to transfer a packet from another input port to this same
output port, the arriving packet is blocked and must be queued at the input port.

4.6

IP Datagram Fragmentation
The problem
Not all link layer protocols can carry network layer packets of the same size. For example, Ethernet
frames can carry up to 1,500 bytes of data, whereas frames for some wide-area links can carry no morethan 576 bytes. The maximum amount of data that a link layer frame can carry is called the maximum
transmission unit (MTU). While forwarding packets, if a router receives a large frame and finds outthat the output link the packet is destined to has a smaller MTU, then what will happen?
The solution – Datagram Fragmentation
 When a datagram is created, the sending host stamps the datagram with source anddestination IP addresses as well as an identification number. Typically, the sending hostincrements the identification number for each datagram it sends.

22 When a router needs to fragment a datagram, each resulting datagram (i.e., fragment) is
stamped with the source and destination IP and identication number of the original
datagram.
Also, in order to for the destination host to determine whether a fragment is missing (andalso to be able to reassemble the fragments in their proper order), an offset field is used to
specify where the fragment fits within the original IP datagram.
Because IP is an unreliable service, one or more of the fragments may never arrive at thedestination. For this reason, in order for the destination host to be absolutely sure it hasreceived the last fragment of the original datagram, the last fragment has a flag bit set to 0,
whereas all the other fragments have this flag bit set to 1.
 The job of datagram reassembly is implemented in the end systems rather than in networkrouters in order to keep the network core simple.
 The payload of the datagram is passed to thetransport layer at the destination only after the IP
layer has fully reconstructed the original IP
datagram. If one or more of the fragments does not
arrive at the destination, the incomplete datagram isdiscarded and not passed to the transport layer.
Consider an example illustrated in the figure on the right. A
datagram of 4,000 bytes (20 bytes of IP header + 3,980 bytes
of payload) arrives at a router and mulst be forwarded to a linkwith an MTU of 1,500 bytes. Suppose that the original
datagram is stamped with an identification number of x. The
characteristics of the three fragments are shown below:
Fragment
Bytes
stData = 1,480 bytes
1
Header = 20 bytes
Data = 1,480 bytes
2nd
Header = 20 bytes
3rd

Data = 1,020 bytes(= 3980-1480-1480)
Header = 20 bytes

ID
Offsetx 0(means the data should be inserted beginnning at byte 0)
x 185(means the data should be inserted beginnning at byte 1480.
Note that 185 × 8 = 1480)
x 370(means the data should be inserted beginnning at byte 2960.
Note that 370 × 8 = 2960)

Flag
1
1

0

The values in the above table reflect the requirement that the amount of original payload data in all
but the last fragment be a multiple of 8 bytes, and that the offset value be specified in units of 8-byte
chunks.
4.7

IPv4 Datagram Format
Version: Protocol version: IPv4, IPv6.
Type of Service: Vendor Specific Service.
Datagram Length: (Header + Data) length.
Identifier, Flags, Offset: For fragmentation.
TTL: Hop count.
Upper-layer Protocol: TCP, UDP etc.

23

4.8

Why error checking is performed at both transport and network layers?
1. Only the IP header is checksummed at the IP layer, while the TCP/UDP checksum is computed
over the entire TCP/UDP segment.
2. TCP/UDP and IP do not necessarily both have to belong to the same protocol stack. TCP can,in principle, run over a different protocol (e.g. ATM) and IP can carry data that will not bepassed to TCP/UDP.

4.9

IPv4 Addressing
Notation
1. Binary:
2. Dotted-Decimal:
3. Hexadecimal:

4.10

10000000 00001011 00000011 00011111
128 .
11
.
3
.
31
0x
80
0B
03
1F

Classful Addressing
In classful addressing, the IP address space is divided into five classes: A, B, C, D and E. Eachclass occupies some part of the whole address space.
Recognizing Classes
First Byte

Second Byte

Third Byte

Fourth Byte

Class A 0
Start
Class B

10Class C

110

1st
Bit?

Class D 1110
Class E

1

0

1111

Class A

0 to 127Class B

128 to 191

Class C

192 to 223

Third Byte

4th
Bit?

Class: C

1

0
Class: D

Fourth Byte

Class
A
B
C
D
E

240 to 255

Number of Addresses
231
230
229
228
228

Percentage
50%
25%
12.5%
6.25%
6.25%

Addresses per classFinding the class in decimal notation

Netid, Hostid and Blocks
In classful addressing, an IP address in classes A, B and C is divided into netid and hostid.
Byte 1

Class AClass BClass: E

Finding the address classClass D 224 to 239
Class E1

0Class: B

Finding the class in binary notation
Second Byte

3rd
Bit?

0

Class: A

First Byte

1

2nd
Bit?

Byte 2

Netid

Byte 3

Byte 4

HostidNetid

HostidClass C

Netid

Class D

Multicast Address

Class E

Reserved for Future Use
24

HostidEach class is divided into a fixed number of blocks with each block having a different netid. For
example, class A is divided into 128 blocks:
The 1st block covers addresses from 0.0.0.0 to 0.255.255.255 (netid 0).
The 2nd block covers addresses from 1.0.0.0 to 1.255.255.255 (netid 1).
The last block covers addresses from 127.0.0.0 to 127.255.255.255 (netid 127).
Similarly, class B is divided into 128 × 128 = 16,384 blocks:
The 1st block covers addresses from 128.0.0.0 to 128.0.255.255 (netid 128.0).
The last block covers addresses from 191.255.0.0 to 191.255.255.255 (netid 191.255).
Note that for each block of addresses, the netid is the same, but the hostid can take any value in thegiven range.
Special Addresses
Special Address
Netid
Hostid Source or Destination
ExampleNetwork address
Specific All 0s
None
141.14.0.0
Direct broadcast address
Specific All 1s
Destination
141.14.3.255
Limited broadcast address
All 1sAll 1sDestination
255.255.255.255
This host on this network
All 0s
All 0s
Source0.0.0.0
Specific host on this network All 0s SpecificDestination
0.0.3.64
Loopback address
127
Any
Destination
127.0.0.1

Network Address
The first address in a block (in classes A, B and C) is called the network address and is used to
identify the organization to the rest of the internet. It defines the network of the organization, notindividual hosts.
Properties of Network Addresses
1. The network address is the first address in the block.
2. The network address defines the network to the rest of the internet.
3. Given the network address, we can find the class of the address, the block, and the range of theaddresses in the block.
Finding class, netid of the block and range of addresses from a network address
Consider the network address 132.21.0.0.
The class is B, because the first byte is between 128 and 191.
The block has a netid of 132.21.
The addresses range from132.21.0.0 to 132.21.255.255.
Masking – Finding the network address from a given address
A mask is a 32-bit number that gives the first address in the block (the network address) when
bitwise ANDed with an address in the block. In the AND operation for classful addressing, there
are three masks, one for each class. The following table shows the default mask for each class:Class
Mask in BinaryA
11111111 00000000 00000000 00000000
B
11111111 11111111 00000000 00000000
C
11111111 11111111 11111111 00000000

Mask in Dotted-Decimal
255.0.0.0
255.255.0.0
255.255.255.0

Direct Broadcast Address
In classes A, B and C, if the hostid is all 1s, the address is called a direct broadcast address. It is
used by a router to send a packet to all hosts in a specifc network.
Limited Broadcast Address
In classes A, B and C, an address with all 1s for the netid and hostid defines a broadcast address in25

the current network. A host that wants to send a message to every other host can use this address as adestination address in an IP packet. However, a router will block a packet having this type of address
to confine the broadcasting to the local network. Note that this address belongs to class E.
This host on this network
If an IP address is composed of all zeroes, it means this host on this network. This is used by a hostat bootstrap time when it does not know its IP address. The host sends an IP packet to a bootstrap
server using this address as the source address and a limited broadcast address as the destination
address to find its own address.
Specific host on this network
An IP address with a netid of all zeroes means a specific host on this network. It is used by a hostto send a message to another host on the same network.
Loopback Address
The IP address with the first byte equal to 127 is used for the loopback address, which is an addressused to test the software on a machine. When this address is used, a packet never leaves the machine; it
simply returns to the protocol software.
Private Addresses
A number of blocks in each class are assigned for private use. They are not recognized globally.
These blocks are depicted in the following table:
Class
NetidsA
10.0.0B
172.16 to 172.31
C
192.168.0 to 192.168.255

Blocks1
16256Unicast, Multicast and Broadcast Addresses
Unicast communication is one-to-one. When a packet is sent from an individual source to anindividual destination, a unicast communication takes place.
Multicast communication is one-to-many. When a packet is sent from an individual source to agroup of destinations, a multicast communication takes place. The entire address defines a groupid. A
system on the internet can have one or more class D multicast addresses (in addition to its unicast
adderss or addresses). If a system has seven multicast addresses, it means that it belongs to sevendifferent groups.
Broadcast communication is one-to-all. The internet allows broadcasting only at the local level.
The Problem with Classful Addressing
Classful addressing means network must be of size 65536 (216) for class B and 256 (28) for class C.
If an organization wants 4 networks each with 300 hosts, then it needs 4 class B networks.
Consequently, more than 200,000 addresses are wasted.
Subnetting
Subnetting was introduced in 1980s to solve this problem. In subnetting, a network is divided into
subnets (short for subnetworks).

Example of a network which is not subnetted
26

Example of a subnetted network

In the example above, only R1, R2 and R3 need to know about the subnets. Each subnet requires
an entry in their routing table. Routers external to the network need not to know about subnetting. In
the figure, the external router requires only an entry for the network address (141.14.0.0) in its routing
table.
Subnetid
141.14.64.1 is an address in the subnet 141.14.64.0 (this is called the subnet address).

Subnet Mask
When we configure a host, we must specify both the IP address of the host and the subnet mask.
The subnet mask has the same role as the network mask; however, it has more 1s.
ExampleFinding the Subnet Address from a Given Address
Consider an IP address 200.45.34.56 and the subnet mask 255.255.240.0. To get the subnet
address, we apply the AND operation on the IP address and the subnet mask.
27

IP Address
Subnet Mask
Subnet Address→→→

11001000 00101101 00100010 00111000
11111111 11111111 11110000 00000000
11001000 00101101 00100000 00000000

The subnet address is 200.45.32.0.
Number of subnetworks
The number of subnetworks can be found by counting the extra 1s that are added to the default
mask to make the subnet mask. For example, in the above example, the number of extra 1s is 3;
therefore, the number of subnets is 24 or 16.
Number of addresses per subnet
The number of addresses per subnet can be found by counting the 0s in the subnet mask. For
example, in the above example, the number of 0s is 12; therefore, the number of possible addresses ineach subnet is 212 or 4096.
Supernetting
If an organization wants 1000 addresses, supernetting allows 4 class C networks to be merged toform a supernet with 1024 addresses.

A supernetwork

Supernet address assignment rules
If a supernet consists of 100 class C networks and if the addresses are randomly chosen, then therouters external to the supernet will require 100 entries for the supernet. It would be desirable if only 1entry is required. This can be achieved by carefully assigning addresses:
1. The number of blocks must be a power of 2 (1, 2, 4, 8, 16, …).
2. The blocks must be contiguous in the address space (i.e., no gaps between the blocks).
3. The third byte of the first address in the superblock must be evenly divisible by the number ofblocks. In other words, if the number of blocks is N, the 3rd byte must be divisible by N.
ExampleA company needs 600 addresses. Which of the following set of class C blocks can be used to forma supernet for this company?
a. 198.47.32.0 198.47.33.0 198.47.34.0
Not acceptable. Number of blocks is 3, which is not a power of 2.
b. 198.47.32.0 198.47.42.0 198.47.52.0 198.47.62.0
Not acceptable. Blocks are not contiguous.
c. 198.47.31.0 198.47.32.0 198.47.33.0 198.47.34.0
Not acceptable. 3rd byte of first address is not divisible by 4 (number of blocks).
d. 198.47.32.0
Acceptable.

198.47.33.0

198.47.34.0
28

198.47.35.0

Supernet Mask
A supernet mask is the reverse of a subnet mask. A subnet mask for class C has more 1s than thedefault mask for this class. A supernet mask for class C has less 1s than the default mask for this class.
The following figure shows the difference between a subnet mask and a supernet mask. A subnet
mask that divides a block into eight subblocks has 3 more 1s (23 = 8) than the default mask; a supernet
mask that combines eight blocks into one superblock has 3 less 1s than the default mask.

Example 1
We need to make a supernetwork out of 16 class C blocks. What is the supernet mask?
Solution: For 16 blocks, we need to change four 1s to 0s in the default mask. So, the mask is:11111111 11111111 11110000 00000000 or 255.255.240.0.
Example 2Given the first address of a supernet 205.16.32.0 and a supernet mask of 255.255.248.0, how many
blocks are in this supernet and what is the range of addresses?
The supernet mask has 21 1s. The default mask has 24 1s. Since the difference is 3, there are 23 or
8 blocks in this supernet.
The blocks are 205.16.32.0, 205.16.33.0, …, 205.16.39.0.
The range of addresses is: from 205.16.32.0 to 205.16.39.255.
4.11Classless Addressing
The problem with classful addressing
The use of classful addressing has created many problems. Until the mid 1990s, a range ofaddresses meant a block of addresses in class A, B or C. The minimum number of addresses granted toan organization was 256 (class C); the maximum was 16, 777, 216 (class A). In between these limits,an organization could have a class B block or several class C blocks. These address assignments werealways in multiples of 256. However, what about a small business that needed only 16 addresses? Or ahousehold that needed only two addresses?
To resolve the problems of classful addressing, in 1996, the Internet authorities announced a newarchitecture called classless addressing.
Restrictions
1. The number of addresses in a block must be a power of 2 (1, 2, 4, 8, 16, …).
2. The addresses in a block must be contiguous.
3. The first address must be evenly divisible by the number of addresses.
If the address has ≤ 256 addresses, we need to divide the right-most byte only.
If the address has ≥ 256 and ≤ 2562 addresses, we need to check only the two right-most bytes
and so on.

29

Example 1
Which of the following can be the beginning address of a block that contains 16 addresses?
a. 205.16.37.32

b. 190.16.42.44

c. 17.17.33.80

d. 123.45.24.52

Only two are eligible (a and c), because both 32 and 80 are divisible by 16.
Example 2
Which of the following can be the beginning address of a block that contains 1024 addresses?
a. 205.16.37.32

b. 190.16.42.0

c. 17.17.32.0

d. 123.45.24.52

In this case, we need to check two bytes because 1024 = 4 × 256. The right-most byte must be
divisible by 256, and the second byte from the right must be divisible by 4. Only (c) is eligible.
CIDR (Classless Inter-Domain Routing) / Slash Notation
A classless network is usually written as A.B.C.D/n where n specifies the number of 1s in the mask.
The first n bits of A.B.C.D is known as the prefix and n is known as the prefix length. The last (32 –n) bits are known as the suffix.
Finding the Network address, range of a block etc.
These all are similar to the techniques used in subnetting.
Subnetting
We can, of course, have subnetting with classless addressing. The prefix length (n) increases todefine the subnet prefix length.
Finding the Subnet Mask
The number of desired subnets defines the subnet prefix. If the number of subnets is s, the numberof extra 1s in the prefix length is log2s, where s = 2number of extra 1s.
ExampleAn organization is granted the block 130.34.12.64/26. The organization needs 4 subnets. What are
the subnet addresses and the range of addresses for each subnet?
First, we find the number of addresses that can be assigned to each subnet. Since the prefix lengthis 26, the last 6 bits are available as hostid. Hence, the total number of addresses in the block is 64 (26).
If we create 4 subnets, each subnet will have 16 addresses.
Now, let us find the subnet prefix (subnet mask). We need four subnets which means we need to
add two more 1s to the site (netid) prefix. The subnet prefix is then /28.
Therefore, the range of addresses for each subnet is:Subnet 1: 130.34.12.64/28 to 130.34.12.79/28.
Subnet 2: 130.34.12.80/28 to 130.34.12.95/28.
Subnet 3: 130.34.12.96/28 to 130.34.12.111/28.
Subnet 4: 130.34.12.112/28 to 130.34.12.127/28.
4.12

Network Address Translation (NAT)
Suppose that an ISP has allocated a contiguous block of addresses to an organization. What if thesubnet of the organization grows bigger? Fortunately, there is a simpler approach to address allocationthat has found increasingly widespread use in such scenarios: NAT.
A NAT-enabled router does not look like a router to the outside world. Instead, the NAT router
behaves to the outside world as a single device with a single IP address.
How NAT Works
Consider the following example.

30

1. Suppose, host 10.0.0.1 requests a web page on some web server with IP 128.119.40.186. The
host 10.0.0.1 assigns the (arbitrary) source port number 3345 and sends the datagram into theLAN.
2. The NAT router receives the datagram, generates a new source port number 5001 for the
datagram, replaces source IP with its WAN-side IP 138.76.29.7, and replaces the original
source port number 3345 with the new source port number 5001. An entry into the NATtranslation table is also entered.
3. The web server, unaware that the arriving datagram containing the HTTP request has been
manipulated by the NAT router, responds with a datagram whose destination IP is the IP of the
NAT router and destination port number is 5001.
4. When this datagram arrives at the NAT router, the router indexes the NAT translation tableusing the destination IP and port number to obtain the appropriate IP address (10.0.0.1) anddestination port number (3345) for the browser. The router then rewrites the datagram’s
destination address and destination port number, and forwards the datagram into the home
network.
Objections to NAT
1. Port numbers are meant to be used for addressing processes, not for addressing hosts.
2. Routers are supposed to process packets up to layer 3.
3. NAT protocol violates the so-called end-to-end argument; i.e., host should be talking directlywith each other, without interfering nodes modifying IP addresses and port numbers.
4. We should use IPv6 to solve the shortage of IP addresses, rather than recklessly patching up the
problem with a stopgap solution like NAT.
Problem of NAT with P2P Applications
 In a P2P application, any participating peer A should be able to initiate a TCP connection to
any other participating peer B.
 Now, if peer B is behind a NAT, it cannot act as a server and accept TCP connections(unless the NAT is specifically configured for the P2P application).
 This problem can be circumvented if peer A first contacts peer B through an intermediatepeer C which is not behind a NAT and to which B has established an on-going TCP
connection. Peer A can then ask peer B, via peer C, to initiate a TCP connection directly
back to peer A.
 This hack, called connection reversal, is actually used by many P2P applications. But if
both peer A and peer B are behind their own NATs, then, for all practical purposes, it is
impossible to establish a TCP connection between the two peers without applicationspecific NAT configuration.
31

4.13

Internet Control Message Protocol (ICMP)ICMP is used by hosts and routers to communicate network-layer information to each other. The
most typical use of ICMP is for error reporting.
ICMP messages have a type and a code field, and contain the header and the first 8 bytes of the IP
datagram that caused the ICMP message to be generated in the first place (so that the sender candetermine the datagram that caused the error).

4.14

IPv6
Important changes introduced in IPv6 datagram format:
1. Expanded addressing capabilities.
 Size of IP address is increased from 32 to 128 bits.
 In addition to unicast and multicast addresses, IPv6 has introduced a new type ofaddress, called an anycast address, which allows a datagram to be delivered to any oneof a group of hosts that have the same prefix. (This feature could be used, for example,
to send an HTTP GET to the nearest of a number of mirror sites that contain a given
document.)
2. A streamlined 40-byte fixed-length header.
3. Flow labeling and priority.
This allows labeling of packets belonging to particular flows for which the sender requests
special handling, such as nondefault quality of service or real-time service.
IPv6 Datagram Format
Traffic class: Similar to TOC field in IPv4.
Next header: Similar to protocol field in IPv4.

Hop limit: Similar to TTL field in IPv4.
Fields no longer present in IPv6 datagram Fragmentation / Reassembly
If an IPv6 datagram received by a router
is too large to be forwarded over theoutgoing link, the router simply drops thedatagram and sends a “Packet Too Big” ICMP error message back to the sender. The sender canthen resend the data using a smaller IP datagram size.
 Header Checksum
 Options
IPv6 Address Format: Hexadecimal Colon Notation

Abbreviation of Addresses
1. Leading zeroes of a section (four digits between two colons) can be omitted. Only the leading
zeroes can be omitted, not the trailing zeroes.
Using this form of abbreviation, 0074 can be written as 74, 000F as F, and 0000 as 0. Note that
3210 cannot be abbreviated.
32

2. If there are consecutive sections consisting of zeroes only, then the zeroes can be removed
altogether and they are replaced with a double semicolon.
Note that this type of abbreviation is allowed only once per address. If there are two runs ofzero sections, only one of them can be abbreviated.
Transitioning from IPv4 to IPv6
How will the public internet, which is based on IPv4, be transitioned to IPv6? The problem is thatwhile new IPv6-capable systems can be made backward-compatible, that is, can send, route andreceive IPv4 datagrams, already deployed IPv4-capable systems are not capable of handling IPv6
datagrams.
Two techniques are as follows:
Dual-Stack Suppose node A wants to send an
IP datagram to node F, both ofwhomare
IPv6-capable.
However, node B must create an
IPv4 datagram to send to C.
 The data field of the IPv6
datagram is copied into the data field of the IPv4 datagram and appropriate address mapping is
done.
 However, in performing the conversion from IPv6 to IPv4, there will be IPv6-specific fields in
the IPv6 datagram that have no counterpart in IPv4. The information in these fields will be lost.
Tunneling With tunneling, the IPv6 node on
the sending side of the tunnel (forexample, B) takes the entire IPv6
datagram and puts it in the data
(payload) field of an IPv4
datagram.
 This IPv4 datagram is then sent
to the first node in the tunnel (forexample, C).
 The intervening IPv4 routers in
the tunnel route this IPv4
datagram among themselves.
 The IPv6 node on the receivingside of the tunnel eventually
receives the IPv4 datagram (it isthe destination of the IPv4
datagram), determines that the IPv4 datagram contains an IPv6 datagram, extracts the IPv6
datagram, and then routes the IPv6 datagram exactly as it would if it had received the IPv6
datagram from a directly connected IPv6 neighbor.
33

Converting IPv6 address into IPv4 address
During transition from IPv4 to IPv6, hosts can use their IPv4 addressees embedded in IPv6
addresses. Two formats have been designed for this purpose: compatible and mapped.
Compatible Address
Used when an IPv6-compatible node wants to send packets to another IPv6-compatible node via
IPv4-compatible nodes.

Mapped Address
Used when an IPv6-compatible node wants to send a packet to a node capable of IPv4 only.

4.15

Routing Algorithms
The purpose of a routing algorithm is simple: given a set of routers, with links connecting therouters, a routing algorithm finds a “good” path from source router to destination router. Typically, agood path is one that has the least cost.
Classifications of Routing Algorithms
Global and Decentralized Routing Algorithms
A global routing algorithm computes the least-cost path between a source and destination using
complete, global knowledge about the network. In practice, algorithms with global state information
are often referred to as link-state (LS) algorithm, since the algorithm must be aware of the cost of eachlink in the network.
In a decentralized routing algorithm, the calculation of the least-cost path is carried out in an
iterative, distributed manner. No node has complete information about the costs of all network links.
Instead, each node begins with only the knowledge of the costs of its own directly attached links.
Then, through an iterative process of calculation and exchange of information with its neighboring
nodes, a node gradually calculates the least-cost path to a destination. The decentralized routing
algorithm we’ll study is called a distance-vector (DV) algorithm, because each node maintains a vectorof estimates of the costs (distances) to all other nodes in the network.
Static and Dynamic Routing Algorithms
In static routing algorithms, routes change very slowly over time, often as a result of humanintervention (for example, a human manually editing a router’s forwarding table).
Dynamic routing algorithms change the routing paths as the network traffic loads or topology
change. A dynamic routing algorithm can be run either periodically or in direct response to topology orlink cost changes. While dynamic algorithms are more responsive to network changes, they are also
more susceptible to problems such as routing loops and oscillation in routes.
34

Load-sensitive and Load-insensitive Routing Algorithms
In a load-sensitive algorithm, link costs vary dynamically to reflect the current level of cogestion in
the underlying link. If a high cost is associated with a link that is currently congested, a routing
algorithm will tend to choose routes around such a congested link.
Today’s internet routing algorithms are load-insensitive, as a link’s cost does not explicitly reflect
its current (or recent past) level of congestion.
4.16

The Link-State (LS) Routing Algorithm
The link-state routing algorithm is known as the Dijkstra’s algorithm. Dijkstra’s algorithm isiterative and has the property that after the kth iteration of the algorithm, the least-cost paths are know
to k destination nodes, and among the least-cost paths to all destination nodes, these k paths will havethe k smallest costs.
Complexity of LS Algorithm
Total number of nodes searched through over all the iterations = n +(n – 1) + (n – 2) + … + 1=


∴ Worst-case complexity = O(n ).
2

A more sophisticated implementation of this algorithm, using a data structure known as a heap, canfind the minimum cost in logarithmic rather than linear time, thus reducing the complexity toO(nlogn).
4.17

The Distance-Vector (DV) Routing Algorithm
The distance vector (DV) algorithm is iterative, asynchronous, and distributed.
It is distributed in that each node receives some information from one or more of its directly
attached neighbors, performs a calculation, and may then distribute the results of its calculation back to
its neighbors.
It is iterative in that this process continues on until no more information is exchanged between
neighbors.
The algorithm is asynchronous in that it does not require all of the nodes to operate in lock stepwith each other.
The Bellman-Ford equationdx(y) = minv {c(x, v) + dv(y)}Here, dx(y) = cost of the least-cost path from node x to node y
The minv in the equation is taken over all of x’s neighbors, v.
Basic Idea of DV algorithm
 Each node x begins with Dx(y), an estimate of the cost of the least-cost path from itself to nodey, for all nodes in N.
Let, Dx = [Dx(y) : y ϵ N] be node x’s distance vector, which is the vector of cost estimates fromx to all other nodes y in N.
 Each node x maintains the following routing data:•

For each neighbor v, the cost c(x, v) from x to directly attached neghbor, v.

•

Node x’s distance vector, that is, Dx = [Dx(y) : y ϵ N], containing x’s estimate of its cost to
all destinations, y in N.

•

The distance vectors of each of its neighbors, i.e., Dv = [Dv(y) : y ϵ N] for each neighbor v ofx.
35 In the distributed, asynchronous algorithm, from time to time, each node sends a copy of its
distance vector to each of its neighbors. When a node x receives a new distance vector from anyof its neighbors, v, it saves v’s distance vector, and then uses the Bellman-Ford equation to
update its own distance vector as follows:
Dx(y) = minv {c(x, v) + Dv(y)}for each node y ϵ N If node x’s distance vector has changed as a result of this update step, node x will then send its
updated distance vector to each of its neighbors, which can in turn update their own distancevectors.
ExampleThe leftmost column of the figure displays
three initial routing tables for each of the threenodes x, y and z.
Within a specific routing table, each row is
a distance vector – specifically, each node’s
routing table includes its own distance vector
and that of each of its neighbors. Thus, the firstrow in node x’s initial routing table is Dx =[Dx(x), Dx(y), Dx(z)] = [0, 2, 7]. The second andthird rows in this table are the most recently
received distance vectors from nodes y and z,
respectively. Because at initialization, node x
has not received anything from y or z, theentries in the 2nd and 3rd rows are initialized toinfinity.
After initialization, each node sends its
distance vector to each of its two neighbors. For
example, node x sends its distance vector Dx =[0, 2, 7] to both y and z. After receiving the
updates, each node recomputes its own distancevector. For example, node x computes:
Dx(x) = 0
Dx(y) = min {c(x, y) + Dy(y), c(x, z) + Dz(y)}= min {2 + 0, 7 + 1} = 2
Dx(z) = min {c(x, y) + Dy(z), c(x, z) + Dz(z)} = min {2 + 1, 7 + 0} = 3
The second column therefore displays, for each node, the node’s new distance vector along with
distance vectors just received from its neighbors. Note, for example, that node x’s estimate for the least
cost to node z, Dx(z) has changed from 7 to 3. Also note that for both nodes y and z, node y achieves
the corresponding minimums. Thus, at this stage of the algorithm, the next-hop routers are v*(y) = y
and v*(z) = y, where v* is the neighboring node that achieves the minimum.
After the nodes recompute their distance vectors, they again send their updated distance vectors totheir neighbors (if there has been a change). This is illustrated in the figure by the arrows from the 2ndcolumn of tables to the 3rd column of tables. Note that only nodes x and z send updates: node y’s
distance vector didn’t change so node y doesn’t send an update. After receiving the updates, the nodes
then recompute their distance vectors and update their routing tables, which are shown in the 3rdcolumn.
The process of receiving updated distance vectors from neighbors, recomputing routing table
entries, and informing neighbors of changed costs of the least-cost path to a destination continues until
no update messages are sent. At this point, the algorithm will enter a quiescent state and remain there
until a link cost changes.
36Changes in Link Cost and Link Failure
Increase in Link Cost
The following figure (a) illustrates a scenario where the link cost from y to x changes from 4 to 1.
We focus here only on y and z’s distance table entries to destination x. The DV algorithm causes thefollowing sequence of events to occur: At time t0, y detects the link cost change (the cost has changed from 4 to 1), updates its
distance vector and informs its neighbors of this change since its distance vector has changed.
 At time t1, z receives the update from y and then updates its table. Since it computes a newleast cost to x (it has decreased from a cost of 5 to a cost of 2), it informs its neighbors.
 At time t2, y has receives z’s update and updates its distance table. Y’s least costs do notchange and hence y does not send any message to z. The algorithm comes to a quiescent state.

Decrease in Link Cost: Emergence of Routing Loop and Count-to-Infinity Problem
Suppose that the link cost between x and y increases from 4 to 60 as shown in the above figure (b).
 Before the link cost changes, Dy(x) = 4, Dy(z) = 1, Dz(y) = 1 and Dz(x) = 5. At time t0, y detects
the link cost change (the cost has changed from 4 to 60). y computes its new minimum cost
path to x to have a cost ofDy(x) = min {c(y, x) + Dx(x), c(y, z) + Dz(x)} = min {60 + 0, 1 + 5} = 6
Of course, with our global view of the network, we can see that this new cost via z is wrong.
But the only information node y has is that its direct cost to x is 60 and that z has last told z thatz could get to x with a cost of 5. So, in order to get to x, y would now route through z, fully
expecting that z will be able to get to z with a cost of 5. As of t1, we have a routing loop – inorder to get to x, y routes through z, and z routes through y. A routing loop is like a black hole –a packet arriving at y or z as of t1 will bounce back and forth between these two nodes forever(or until the routing tables are changed).
 Since node y has computed a new minimum cost to x, it informs z of this new cost at time t1.
 Sometime after t1, z receives the new least cost to x via y (y has told z that y’s new minimum
cost is 6). z knows it can get to y with a cost of 1 and hence computes a new least cost to z (still
via y) of 7. Since y’s least cost to x has increased, it then informs y of its new cost at t2.
 In a similar manner, y then updates its table and informs z of a new cost of 8. z then updates its
table and informs y of a new cost of 9 and so on…
This process will persist for 44 iterations until z eventually computes the cost of its path via y to begreater than 50. At this point, z will determine that its least-cost path to x is via its direct connection tox. y will then route to x via z.
What would have happened if the link cost c(y, x) had changed from 4 to 10,000 and the cost c(z, x)
had been 9,999? This problem is sometimes referred to as count-to-infinity problem.
Poisoned Reverse
The specific looping scenario just described can be avoided using a technique known as poisoned
reverse. The idea is simple – if z routes through y to get to destination x, then z will advertise to y thatits (z’s) distance to x is infinity. z will continue telling this little “white lie” to y as long as it routes to x
via y. Since y believes that z has no path to x, y will never attempt to route to x via z, as long as z
37

continues to route to x via y (and lie about doing so).
Let’s now see how poisoned reverse solves the particular looping problem we encountered before.
As a result of the poisoned reverse, y’s distance table indicates an infinite cost when routing to x via Z(the result of z having informed y that z’s cost to x was infinity). When the cost of the xy link changes
from 4 to 60 at time t0, y updates its table and continues to route directly to x, albeit at a higher cost of60, and informs z of this change in cost. After receiving the update at t1, z immediately shifts it route
to x to be via the direct zx link at a cost of 50. Since this is a new least cost to x, and since the path nolonger passes through y, z informs y of this new least cost path to x at t2. After receiving the updatefrom z, y updates its distance table to route to x via z at a least cost of 51. Also, since z is now on y’s
least path to x, y poisons the reverse path from z to x by informing z at time t3 that it (y) has an infinite
cost to get to x.
Does poison reverse solve the general count-to-infinity problem? It does not. Loops involving threeor more nodes (rather than simply two immediately neighboring nodes, as we saw in Figure 4.31) will
not be detected by the poison reverse technique.
4.18

Comparison of LS and DV Routing Algorithms
LS

DV

Message complexity

With N nodes and E links, O(|N||E|) Messages need to be exchanged
messages need to be sent.
among neighbors only.

Speed of convergence

O(|N|2) algorithm requiring O(|N||E|)messages.

-

Can converge slowly.
Can have routing loops whileconverging.
Can suffer from count-toinfinity problem.

Robustness: what happens As an LS node is only computing its A node can advertise incorrect
own routing table, route calculations are least path costs to any/all
if a router malfunctions?
somewhatseparated
underLS, destinations.
providing a degree of robustness.

4.19

Hierarchical Routing
In our study of LS and DV algorithms, our view of the network simply as a collection ofinterconnected routers has two limitations:
1. Scale.
As the number of routers becomes large, the overhead involved in computing, storing andcommunicating the routing table information (e.g., link state updates or least cost path changes)
becomes prohibitive. Today’s public Internet consists of millions of interconnected routers andmore than 50 million hosts. Storing routing table entries to each of these hosts and routers
would clearly require enormous amounts of memory.
2. Administrative Autonomy.
Although engineers tend to ignore issues such as a company’s desire to run its routers as it
pleases (e.g., to run whatever routing algorithm it chooses), or to hide aspects of the networks’internal organization from the outside, these are important considerations. Ideally, anorganization should be able to run and administer its network as it wishes, while still being able
to connect its network to other outside networks.
Autonomous Systems (AS)
Both of these problems can be solved by organizing routers into autonomous systems (AS), witheach AS consisting of a group of routers that are typically under the same administrative control.
 Routers within the same AS all run the same routing algorithm.
 The routing algorithm running within an autonomous system is called an intra-autonomous
system routing protocol or interior gateway protocols.
38 It will be necessary, of course, to connect Ass to each other, and thus one or more of the routersin an AS will have the added task of being responsible for forwarding packets to destinations
outside the AS; these routers are called gateway routers.

How does a router within some AS know how to route a packet to a destination that is outside
the AS?
 It’s easy to answer this question if the AS has only one gateway router that connects to only
one other AS. The router would simply choose the least-cost path to the gateway router andsend the packet to it. The gateway router would forward the packet outside the AS.
 If the AS has more than one gateways (e.g., AS1 in the above figure), then the problem ofknowing where to forward the packet becomes more challenging. To solve this, the AS needs
1. to learn which destinations are reachable via which AS (e.g., which are via AS2 and which
are via AS3).
2. to propagate this reachability information to all the routers within the AS (AS1), so thateach router can configure its forwarding table to handle external-AS destinations.
 These two tasks are handled by the inter-AS routing protocol.
 Since the inter-AS routing protocol involves communication between two Ass, the two
communicating Ass must run the same inter-AS routing protocol. In fact, in the internet, all Ass
run the same inter-AS routing protocol called BGP4.
 Each router receives information from an intra-AS routing protocol and an inter-AS routing
protocol and uses the information from both protocols to configure its forwarding table.
- For example, if AS1 learns from inter-AS routing protocol that subnet x is reachable via
only AS3, all the routers in AS1 will add an entry to their table that to send a packet todestination x, it must be forwarded to gateway 1c.
- Again, if AS1 learns from inter-AS routing protocol that subnet x is reachable via both AS2
and AS3, all the routers in AS1 will add an entry to their table that to send a packet todestination x, it must be forwarded to the gateway having the least-cost path from therouter.
 When an AS learns about a destination from a neighboring AS, the AS can advertise thisrouting information to some of its other neighboring ASs.
- For example, suppose AS1 learns from AS2 that subnet x is reachable via AS2. AS1 could
then tell AS3 that x is reachable via AS1.
39

4.20

Intra-AS Routing in the Internet: RIP (Routing Information Protocol)
 RIP is a DV protocol.
 RIP uses hop count as cost metric; i.e.,each link has a cost of 1. Costs are
actually from source router to a
destination subnet rather than between apair of routers. RIP uses the term hop,which is the number of subnets traversed
along the shortest path from source
router to destination subnet. The figure
beside illustrates an AS with six leaf subnets. The table in the figure indicates the number ofhops from the source A to all the leaf subnets.
 The maximum cost of a path is limited to 15, thus limiting the use of RIP to autonomous
systems that are fewer than 15 hops in diameter.
 Routing updates are exchanged between neighbors approximately every 30 seconds using a
RIP response message. The response message sent by a router or host contains a list of up to
25 destination subnets within the AS, as well as the sender’s distance to each of those subnets.
Response messages are also known as RIP advertisements.
 If a router does not hear from its neghbor at least once every 180 seconds, that neighbor isconsidered to be no longer reachable. When this happens, RIP modifies the local routing table
and then propagates this information by sending advertisements to its neighboring routers.
 A router can also request information about its neighbor’s cost to a given destination using
RIP’s request message. Routers send RIP request and response messages to each other over
UDP using port number 520. (In this case, RIP is implemented as an application layer protocol
in a UNIX system serving as a router.)
How RIP Advertisement Works
Consider the portion of an AS shown in
the figure beside. Each router maintains a RIP
table known as a routing table. A router’srouting table includes both the router’s
distance vector and the router’s forwarding
table. Figure 4.36 shows the routing table forrouter D.
Now suppose that 30 seconds
later, router D receives from router
A the advertisement shown infigure 4.37. Note that thisadvertisement is nothing other than
the routing table information fromrouter A.
Router D, upon receiving thisadvertisement,
mergestheadvertisement with the old routing
table. In particular, router D learns
that there is now a path throughrouter A to subnet z that is shorter
than the path through router B.
Thus, router D updates its routing
table to account for the shorter
shortest path.
40

4.21

Intra-AS Routing in the Internet: OSPF (Open Shortest Path First)
 OSPF and its closely related cousin, IS-IS, are typically deployed in upper-tier ISPs whereas
RIP is deployed in lower-tier ISPs and enterprise networks.
 A router broadcasts a link’s state periodically (at least every 30 minutes) to all other routers in
the AS, even if the link’s state has not changed.
 OSPF advertisements are contained in OSPF messages that are carried directly by IP, with an
upper-layer protocol of 89 for OSPF.
 An OSPF AS can be configured into areas. Each area runs its own OSPF link-state routing
algorithm.
 Within each area, one or more area border routers are responsible for routing packets outside
the area.
 Exactly one OSPF area in the AS is configured to be the backbone area. The primary role ofthe backbone area is to route traffic between the other areas in the AS. The backbone always
contains all area border routers in the AS and may contain nonborder routers as well.
 Inter-area routing within the AS requires that the packet be first routed to an area border router(intra-area routing), then routed through the backbone to the area border router that is in thedestination area, and then routed to the final destination.
 A boundary router exchanges routing information with routers belonging to other ASs. Thisrouter might, for example, use BGP to perform inter-AS routing. It is through such a boundaryrouter that other router learn about paths to external networks.

41

CHAPTER 5
LINK LAYER
What we are going to discuss in this chapter
1. The services provided by link layer
2. Error detection and correction techniques
a. Parities and FEC (Forward Error Correction)
b. Checksum
c. CRC (Cyclic Redundancy Check)
3. Multiple Access Protocols
a. Channel Partitioning Protocols
i. TDMA (Time Division Multiple Access)ii. FDMA (Frequency Division Multiple Access)iii. CDMA (Code Division Multiple Access)b. Random Access Protocols
i. Slotted ALOHA
ii. ALOHA
iii. CSMAc. Taking Turns Protocol
i. Reservation
ii. Pollingiii. Token Passing
4. Link-layer addressinga. MAC (Media Access Control)b. ARP (Address Resolution Protocol)c. DHCP (Dynamic Host Configuration Protocol)
5. Ethernet: Details of the implementation of a multiple access protocol (CSMA/CD)
6. Hubs and Switches: Interconnections among LANs
7. PPP (Point-to-point Protocol)

42

5.1

Types of link-layer channels
There are two fundamentally different types of link-layer channels:
1. Broadcast Channels:
Many hosts are connected to the same communication channel, and a so-called medium
access protocol is needed to coordinate transmissions and avoid collisions.
Examples: LANs, wireless LANs, satellite networks, HFC (Hybrid Fiber Coaxial Cable)
access networks.
2. Point-to-point Communication Link:
Examples: Between two routers, between a residential dial-up modem and as ISP router.

5.2

Link-layer Protocols
1.
2.
3.
4.

5.3

Ethernet
Wi-Fi (802.11 wireless LAN)
Token Ring
PPP (Point-to-Point Protocol)

Some Important Notes
An important characteristic of the link layer is that a datagram may be handled by different linklayer protocols on the different links in the path. For example, a datagram may be handled by Etherneton the first link, PPP on the last link, and frame relay on all intermediate links.
It is important to note that the services provided by the different link-layer protocols may bedifferent. For example, a link-layer protocol may or may not provide reliable delivery. Thus, thenetwork layer must be able to accomplish its end-to-end job in the face of a varying set of individual
link-layer services.

5.4

Adapters / Network Interface Cards (NICs)
For a given communication link, the linklayer protocol is for the most part
implemented in an adapter. Adapters are also
commonly known as network interface cards
or NICs.
As shown in the figure, the main
components of an adapter are the bus interface
and the link interface.
The bus interface is responsible forcommunicating with the adapter's parent
node. It sends to and receives from the parent
node network-layer datagram and control
information.
The link interface is responsible for implementing the link-layer protocol. In addition to framingand de-framing datagram, it may provide error detection, random access and other link-layer
functions. It also includes the transmit and receive circuitry.

5.5

Error Detection and Correction Techniques
General Technique
Before sending, compute the error detection bits and append them to the message. After receiving,
check the whole message and determine whether error has occurred.

43

5.6

Parity Checks
In an even parity scheme, the sender simply includes one
additional bit and chooses its value such that the total number of 1's inthe d + 1 bits (the original information plus a parity bit) is even. For
odd parity schemes, the parity bit value is chosen such that there arean odd number of 1's.
Receiver operation is also simple with a single parity bit. The receiver need only count the numberof 1's in the received d + 1 bits. If an odd number of 1-valued bits are found with an even parity
scheme, the receiver knows that at least one bit error has occurred. More precisely, it knows that some
odd number of bit errors has occurred.
Disadvantage
Occurrence of an even number of bit errors cannot be detected.

5.7

FEC (Forward Error Correction)
Figure 5.2-3 shows a two-dimensional
generalization of the single-bit parity scheme. Here,the d bits in D are divided into i rows and j columns.
A parity value is computed for each row and for eachcolumn. The resulting i + j + 1 parity bits are the datalink frame's error detection bits.
Suppose now that a single bit error occurs in theoriginal d bits of information. With this twodimensional parity scheme, the parity of both thecolumn and the row containing the flipped bit will bein error. The receiver can thus not only detect the factthat a single bit error has occurred, but can use thecolumn and row indices of the column and row withparity errors to actually identify the bit that was
corrupted and correct that error!
The ability of the receiver to both detect andcorrect errors is known as forward error correction(FEC).
Application
These techniques are commonly used in audio storage and playback devices such as audio CD's.
Advantages
1. Decreases the number of sender retransmissions required.
2. Allows for immediate correction of errors at the receiver. This avoids having to wait theround-trip propagation delay needed for the sender to receive a NAK packet and for the
retransmitted packet to propagate back to the receiver – a potentially important advantage forreal-time network applications.

5.8

Internet Checksum

5.9

Cyclic Redundancy Check (CRC)

5.10

Multiple Access Protocols
The Problem
Because all nodes are capable of transmitting frames, more than two nodes can transmit frames atthe same time. When this happens, all of the nodes receive multiple frames at the same time, that is,
the transmitted frames collide at all of the receivers. Typically, when there is a collision, none of thereceiving nodes can make any sense of any of the frames that were transmitted; in a sense, the signals
44

of the colliding frame become inextricably tangled together. Thus, all the frames involved in thecollision are lost, and the broadcast channel is wasted during the collision interval. Clearly, if many
nodes want to frequently transmit frames, many transmissions will result in collisions, and much of
the bandwidth of the broadcast channel will be wasted.
So, how can we coordinate the access of multiple sending and receiving nodes to a shared
broadcast channel?
General Idea for a Solution
In order to ensure that the broadcast channel performs useful work when multiple nodes are active,
it is necessary to somehow coordinate the transmissions of the active nodes. This coordination job isthe responsibility of the multiple access protocol.
What should be the general characteristics of a multiple access protocol
A multiple access protocol for a broadcast channel of rate R bits per second should have thefollowing desirable characteristics:
1. When only one node has data to send, that node has a throughput of R bps.
2. When M nodes have data to send, each of these nodes has a throughput of R/M bps. This need
not necessarily imply that each of the M nodes always have an instantaneous rate of R/M , butrather that each node should have an average transmission rate of R/M over some suitablydefined interval of time.
3. The protocol is decentralized, i.e., there are no master nodes that can fail and bring down theentire system.
4. The protocol is simple, so that it is inexpensive to implement.
Some multiple access protocols
1. Channel Partitioning Protocols: TDMA, FDMA and CDMA
2. Random Access Protocols: Slotted ALOHA, ALOHA, CSMA
3. Taking-Turns Protocols: Polling, Token Passing
5.11

Channel Partitioning Protocols
The broadcast channel's bandwidth is partitioned among all nodes sharing that channel.
TDMA (Time-Division Multiple Access)Suppose the channel supports N nodes and that the transmission rate of the channel is R bps.
TDMA divides time into time frames and further divides each time frame into N time slots. Eachslot time is then assigned to one of the N nodes.
Whenever a node has a frame to send, ittransmits the frame's bits during its assigned
time slot in the revolving TDMA frame.
Typically, frame sizes are chosen so that asingle frame can be transmitting during a slot
time.
Advantages
1. Eliminates collision.
2. Perfectly fair: each node gets a
dedicated transmission rate of R/N bps
during each slot time.
Disadvantages
1. A node is limited to this rate of R/N bps
over a slot's time even when it is the
only node with frames to send.
45

2. A node must always wait for its turn in the transmission sequence – again, even when it is the
only node with a frame to send.
FDMA (Frequency-Division Multiple Access)
FDMA divides the R bps channel into different frequencies (each with a bandwidth of R/N) andassigns each frequency to one of the N nodes. FDMA thus creates N "smaller" channels of R/N bps
out of the single, "larger" R bps channel.
Advantages and Disadvantages
Same as the advantages and disadvantages of TDMA except the second disadvantage.
Code Division Multiple Access (CDMA)
CDMA assigns a different code to each node. Each node then uses its unique code to encode thedata bits it sends. Because CDMA’s use is so tightly tied to wireless channels, we’ll save our
discussion of the technical details of CDMA until chapter 6 (Wireless and Mobile Networks).
5.12

Random Access Protocols
In a random access protocol, a transmitting node always transmits at the full rate of the channel,
namely, R bps. When there is a collision, each node involved in the collision repeatedly retransmits its
frame until the frame gets through without a collision. But when a node experiences a collision, it
doesn't necessarily retransmit the frame right away. Instead it waits a random delay before
retransmitting the frame. Each node involved in a collision chooses independent random delays.
Because after a collision the random delays are independently chosen, it is possible that one of thenodes will pick a delay that is sufficiently less than the delays of the other colliding nodes, and will
therefore be able to "sneak" its frame into the channel without a collision.
Some random access protocols
1.
2.
3.
4.
5.

5.13

Pure ALOHA (Areal Locations Of Hazardous Atmospheres)
Slotted ALOHA
CSMA (Carrier-Sense Multiple Access)
CSMA/CD (CSMA with Collision Detection)
CSMA/CA (CSMA with Collision Avoidance)

General Idea of the ALOHA Protocols
In ALOHA protocols, a node waits for an arbitrary amount of time before sending a new frame or
before retransmitting a frame after a collision.
The amount of time to be waited is said to be a probability, p. p is the probability of taking thedecision that it should send the frame. It’s like tossing a coin; if it’s the head, the node will send theframe, if it’s the tail, it will wait for some fixed amount of time, and then toss again to decide whether
it should send the frame this time.
Pure ALOHA
In pure ALOHA, when a frame first arrives (i.e., a network layer datagram is passed down fromthe network layer at the sending node), the node immediately transmits the frame in its entirety into
the broadcast channel. If a transmitted frame experiences a collision with one or more othertransmissions, the node will then immediately (after completely transmitting its collided frame)
retransmit the frame with probability p. Otherwise, the node waits for a frame transmission time. After
this wait, it then transmits the frame with probability p, or waits (remaining idle) for another frame
time with probability 1 – p.
Slotted ALOHA
The operation of slotted ALOHA in each node is simple:
1. When the node has a fresh frame to send, it waits until the beginning of the next slot and46

transmits the entire
frame in the slot.
2. If there isn't a collision,
the node won't consider
retransmitting
theframe. (The node canprepare a new frame fortransmission, if it hasone.)
3. If there is a collision,
the node detects thecollision before the endof the slot. The node
retransmits its frame ineach subsequent slotwith probability p until
the frame is transmitted without a collision.
Advantages of slotted ALOHA
1. Allows a node to transmit continuously at full rate even when that node is the only activenode.
2. Highly decentralized, because each node detects collisions and independently decides when to
retransmit.
3. Extremely simple protocol.
Efficiency Concerns with ALOHA
Slotted ALOHA also works great when there is only one active node, but how efficient is it when
there are multiple active nodes? There are two possible efficiency concerns here.
1. As shown in Figure 5.11, when there are multiple active nodes, a certain fraction of the slots
will have collisions and will therefore be "wasted."
2. The second concern is that another fraction of the slots will be empty because all active nodes
refrain from transmitting as a result of the probabilistic transmission policy.
The only "unwasted" slots will be those in which exactly one node transmits. A slot in which
exactly one node transmits is said to be a successful slot.
The efficiency of a slotted multiple access protocol is defined to be the long-run fraction of
successful slots when there are a large number of active nodes, with each node having a large numberof frames to send.
Note that if no form of access control were used, and each node were to immediately retransmits
after each collision, the efficiency would be zero. Slotted ALOHA clearly increases the efficiency
beyond zero, but by how much?
Maximum Efficiency of Slotted ALOHA
To keep the derivation of maximum efficiency of Slotted ALOHA simple, let's modify the
protocol a little and assume that each node attempts to transmit a frame in each slot with probability p.
(That is, we assume that each node always has a frame to send and that the node transmits withprobability p for a fresh frame as well as for a frame that has already suffered a collision.)
Let, the number of nodes = N.
Then the probability that a given slot is a successful slot is the probability that one of the nodes
transmits and that the remaining N – 1 nodes do not transmit.
Let, Probability that a given node transmits = p
47 Probability that the remaining N – 1 nodes do not transmit = (1 – p)N – 1
 Probability that a given node has success = p(1 – p)N – 1
 Probability that an arbitrary node (among N nodes) has success = N p(1 – p)N – 1
 Efficiency of Slotted ALOHA = N p(1 – p)N – 1
 Maximum efficiency for N active nodes?
We have to find p* that maximizes the expression N p*(1 – p*)N – 1.
 Maximum efficiency for a large number of nodes?
Let N = ∞After performing these calculations, we'll find that the maximum efficiency of the protocol isgiven by 1/e = .37. That is, when a large number of nodes have many frames to transmit, then (at best)
only 37% of the slots do useful work. Thus the effective transmission rate of the channel is not R bps
but only .37 R bps!
Maximum Efficiency of Pure ALOHA
We focus on an individual
node. We'll make the same
assumptions as in our slotted
ALOHA analysis and take theframe transmission time to be
the unit of time.
At any given time, theprobability that a node istransmitting a frame is p.
Suppose this frame begins
transmission at time t0.
As shown in Figure 5.12, in order for this frame to be successfully transmitted, no other nodes canbegin their transmission in the interval of time [t0-1, t0]. Such a transmission would overlap with the
beginning of the transmission of node i's frame.
The probability that all other nodes do not begin a transmission in this interval is (1 – p)N – 1.
Similarly, no other node can begin a transmission while node i is transmitting, as such atransmission would overlap with the latter part of node i's transmission.
The probability that all other nodes do not begin a transmission in this interval is also (1 – p)N – 1.
Thus, the probability that a given node has a successful transmission is p(1 – p)2(N – 1).
By taking limits as in the slotted ALOHA case, we find that the maximum efficiency of the pure
ALOHA protocol is only 1/(2e) – exactly half that of slotted ALOHA.
Disadvantages of ALOHA
In both slotted and pure ALOHA, a node neither pays attention to whether another node happens
to be transmitting when it begins to transmit, nor stops transmitting if another node begins to interferewith its transmission.

48