Networks

Question 1

What is the difference between host and an end system? List several types of end systems. Is a Web server an end system?

Answer 1

There is no difference. Throughout this text, the words “host” and “end system” are used interchangeably. End systems include PCs, WorkStations, Web servers, mail servers ..

Question 2

What is bandwidth?

Answer 2

The maximum rate of data transfer across a given path.

Question 3

What is a protocol?

Answer 3

A protocol is a set of rules that define format, order of messages sent and received among network entities, and actions taken on message transmission, receipt.

Question 4

What is the difference between DSL and Cable?

Answer 4

DSL (Digital Subscriber Line) uses the existing telephone line. Data over DSL phone line goes to internet, whilst voice over the DSL phone line goes to internet. DSL is asymmetric access - meaning downstream and upstream rates are different.

Question 5

How do Ethernet compare against DSL and cable?

Answer 5

Ethernet is a lot faster speeds could range up to 10Gbps. Typically used in companies/ universities.

Question 6

Describe Twisted pair, coaxial cable and fiber optic cable.

Answer 6

Twisted pair consists of two insulated copper wires twisted around each other (Used in old telephone networks). Coaxial cables consists of two concentric copper conductors that can achieve high data transmission rates bidirectional (used as a transmission line for radio frequency signals). Fibre optic cables are glass fibre that have the ability to carry light pulses (a pulse is a bit) in very fast speeds and greater distances. There is a low error rate as repeaters are spaced far apart and are immune to electromagnetic noise.

Question 7

Is HFC rate dedicated or shared among users? Are collisions possible in a downstream HFC channel? Why or why not?

Answer 7

HFC bandwidth is shared among the users. On the downstream channel, all packets emanate a single source, namely, the head end. Thus, there are are no collisions in the downstream channel.

Question 8

What information is used by a process running on one host to identify a process running on another host?

Answer 8

The IP address of the destination host and the port number of the socket in the destination process.

Question 9

Suppose you wanted to do a transaction from a remote client to a server as fast as possible. Would you use UDP or TCP? Why?

Answer 9

You would use UDP. With UDP, the transaction can be completed in one trip round time (RTT) - the client sends the transaction request into a UDP socket, and have the server sends the reply back to the client’s UPD socket. With TCP a minimum of two RTTs are needed - one to set-up the TCP connection, and another for the client to send the request, and for the server to send back the reply.

Question 10

List the four broad classes of services that a transport protocol can provide. For each of the service classes, indicate if either UDP or TCP (or both) provides such a service.

Answer 10

[1] Reliable data transfer: TCP provides a reliable byte-stream between client and server but UDP does not.
[2] A guarantee that a certain value for throughput (the amount of material or items passing through a system to process) will be maintained: Neither
[3] A guarantee that data will be delivered within a specified amount of time: Neither
[4] Confidentiality (via encryption): Neither

Question 11

What is meant by a handshaking protocol?

Answer 11

A protocol uses handshaking of the two communicating entities first exchange control packets before sending data to each other. SMTP uses handshaking at the application layer whereas HTTP does not.

Question 12

IN TCP, why must the server program be executed before the client program? For the client-server application over UDP, why may the client program be executed before the server program?

Answer 12

For the TCP application, as soon as the client is executed, it attempts to initiate a TCP connection with the server. If the TCP serve his not running, then the client will fail to make a connection. For the UDP application, the client does not initiate connections (or attempt to communicate with the UDP server) immediately upon execution.

Question 13

What is meant by routing?

Answer 13

Routing refers to establishing routes that data packets take on their way to a particular destination.

Question 14

What is meant by forwarding?

Answer 14

Is the process of moving packets from a router’s input to another router output.

Question 15

Describe processing delay.

Answer 15

Time used to examine the packet’s header and determine where to direct it, as well as checking for bit-level errors. (Processing data/packets)

Question 16

Describe Queuing delay.

Answer 16

Time taken for a packet to be transmitted onto the link. Naturally; the length of time is defined by the number of packets the was added to the queue prior to this packet.

Question 17

Describe Transmission delay.

Answer 17

The amount of time used to transmit (push) all of the packets bits from the queue and into the link. To calculate the delay, the L/R , where L is the length of the packet (in bits) , R is the transmission speed of the ethernet link in Mbps.

Question 18

Describe propagation delay.

Answer 18

Time required to propagate from the beginning of the link and to the end. Speed depends on the physical medium in which it travels on. The delay can be calculated by t = d/s.

Question 19

How can packet loss occur?

Answer 19

Packets can be dropped when the rate of transmission (of packets) exceeds the capacity of the receiving end. As packets will have to queue and wait for turn. Thus it is important that the rate of transmission is not higher than the rate of acceptance.

Question 20

What is nodal delay?

Answer 20

Nodal delay is the sum of all delays. nodalDelay = Queue + transmission + propagation + processing.

Question 21

What is circuit switching?

Answer 21

A type of communications in which a dedicated channel (or circuit) is established for the duration of a transmission. E.g Old telephone system

Question 22

What are all the layers?

Answer 22

Application, Transport, Network, Link and Physical.

Question 23

What are the differences between the application layer and transport layer?

Answer 23

Transport layer - The act of moving data between two end points (think of TCP/IP).
Application layer - The application that makes use of that transport (think HTTP or FTP).

Question 24

What does ACKs mean?

Answer 24

Acknowledgements - receiver explicitly tells sender that put received OK.

Question 25

What does NAKs mean?

Answer 25

Negative acknowledgements - receiver explicitly tells sender that put had errors. (Sender retransmits put on receipt of NAK)

Question 26

What is meant by a reliable channel?

Answer 26

No transferred data bits are corrupted (flipped from 0 to 1, or vice versa) or lost, and all are delivered in the order in which they are sent.

Question 27

Describe three properties of a connectionless network data transmission.

Answer 27

Unreliability - packets/data not acknowledged on receipt.
Unconnected - hosts/nodes do not maintain established end to end communication. Or, hosts/nodes do not require a session connection.
Variable routing - all packets or data may follow different routed through the network.
Minimal Services - a connectionless network provides minimal services.
Periodic transfer - useful for periodic burst transfer.

Question 28

Outline the key stages of CSMA (Carrier Sense Multiple Access) / CD (Collision Detection) as it would operate for multiple nodes (i.e. Hosts / computers / devices) connected to a common wired medium of communication.

Answer 28

CSMA works on the principle that only one device can transmit signals on the network, otherwise a collision will occur resulting in the loss of data packets or frames. CSMA works when a device needs to initiate to transfer data over the network. Before transferring, each must check or listen to the network for any other transmissions that may be in progress. If it senses a transmission, the device will wait for it to end. Once the transmission is completed, the waiting device can transmit its data/signals. However, if multiple devices access it simultaneously and collision occurs, they both have to wait for a specific time before reinitiating the transmission process.

Carrier senses medium before transmission. -> if busy, station waits per persistence algorithm - otherwise it transmits the frame and continues to listen. If it detects a collision, it immediately stops transmitting and sends a short jamming signal (analog) after a collision it waits a random amount of time and tries again.

Question 29

In our rdt protocols, why did we need to introduce timers?

Answer 29

To handle losses in the channel. If the ACK for a transmitted packet is not received within the duration of the timer for the packet, the packet (or its ACK or NACK) is assumed to have been lost. Hence, the packet is retransmitted.

Question 30

Describe rdt 1.0.

Answer 30

The underlying channel is perfectly reliable, there are no bit errors and no loss of packets. The sender sends data to the underlying channel and the receiver reads data from it.

Question 31

Describe rdt 2.0.

Answer 31

The underlying channel may flip bits in the packet. Thus a checksum is required to detect bit errors. To recover from errors Automatic Repeat reQuest protocols are used. Where the receiving end sends ACKs (acknowledgements) when the pkt is received ok or NAKs (negative acknowledgements) when the pkt has errors. After a NAK retransmission occurs for the erroneous packets. So there is error detection and feedback control messages from receiver to sender.

Question 32

Does rdt 2.0 have any flaws? If so describe.

Answer 32

Yes - ACKs and NAKs can be corrupted. This the sender doesn’t know what happens at the receiving end and won;t just be able to retransmit. This can be solved by stopping and waiting for each packet response. The receiving end must be able to handle duplicate packets -> each packet is given a sequence number which allows both ends to track which packets to process. Thus the receiving end only needs to discard any duplicates, if found.

Question 33

Describe rdt3.0.

Answer 33

Rdt3.0 attempts to solve the problem that the underlying channel can also lose packets. Checksums, sequence numbers, ACKs and retransmissions will be of help but this is not enough. The approach is that the sender should wait a “reasonable” amount of time for an ACK. If no ACK is received within the time frame then the sender retransmits. Any duplicates are handles by checking sequence numbers. Thus rdt3.0 requires a count down timer!

Question 34

What are pipelined protocols?

Answer 34

A pipelined protocol is the opposite of a stop-and-wait protocol (where ACKs are waited for, for each pkt sent). A pipelined protocol allows multiple transmissions of packets and ACK packets at once. For this to be possible the range of sequence numbers must be increased (as more packets are in play).

Question 35

Describe Go-back-N.

Answer 35

The sender can wait for multiple packets without waiting for ACK. However the sender can only have up to N unacked packets in a pipeline. The sender only sends cumulative acknowledgements meaning it doesn’t acknowledge a packet if there is a gap. The sender has a timer for the oldest unacknowledged packet, so when the timer expires the sender retransmits all unacknowledged packets. - So it’s like a bomb, it’ll retransmit all packets from the unacked packet.

Question 36

Describe selective repeat.

Answer 36

The sender can also have N unacknowledged packets in the pipeline. The receiver sends an individual ack for each packet. The sender maintains a timer for each unacked packet - when the timer expires, retransmit only that unacked packet. So there are multiple timers which is different. - so it’s selective in the packets it retransmits

Question 37

Describe Distance vector routing algorithm.

Answer 37

Each node knows distance of links to its neighbours.
Each node advertises a vector of the lowest known distances to all neighbours.
Each node uses received vectors to update its own.
Repeated periodically.

Each routers maintains a table (i.e. A vector) giving the best known distance to each destination and which link to use to get there. These tables are updated by exchanging information with the neighbours. Eventually, every router knows the best link to reach each destination. Once every T msec,, each router sends to each neighbour.

Question 38

Describe the count-to-infinity problem.

Answer 38

Failures can cause the distance vector to “count to infinity” while seeking a path to an unreachable node. At first packet exchange, B does not hear anything from A. Fortunately, C says “Do not worry; I have a paths to A of length 2” Little does B suspect that C’s path runs through B itself for all B knows, C might have ten links with all seperate paths to A of length 2. As a result, B thinks it can reach A via C, with a path of 3. D and E do not update their entries for A on the first exchange. On the second exchange, C notifies that each of its neighbours claim to have a path to A of length 3. It picks one of them at random and makes its new distance to A 4, as shown in the third row. Subsequently exchanges produce the history of the rest of Fig 5(b) Gradually, all routers work their way up to infinity.

Question 39

Describe link state routing.

Answer 39

Distance vector routing takes too long to converge after the network topology changes (due to the count-to-infinity problem). In link state each router must do the following things to make it work:

1. Discover its neighbours and learn their network addresses.
2. Set the distance or cost metric to each of its neighbours.
3. Construct a (HELLO) packet telling all it has just learned.
4. Send this packet to and receive packets from all other routers.
5. Compute the shortest path to every other router.

In effect, the complete topology is distributed to every router. Then Dijkstra’s algorithm can be run at each router to find the shortest path to every other router.

Question 40

What is Hierarchy routing?

Answer 40

Routers are divided into regions. Each router knows all the details about how to route packets to destinations within its own region but knows nothing about the internal structure of other regions. This results to less computation but longer paths (compared to flat routing).

Question 41

Describe the difference between TDM (time division multiplexing) and FDM (frequency division multiplexing) and why they are used.

Answer 41

In TDM, each use gets the entire transmission capacity for a fixed time interval. Whilst in FDM, each user gets a portion of the transmission capacity for the whole time as each is in a different frequency.

Question 42

What are the limitations for static channel allocations.

Answer 42

• Works only for a fixed number of users.
  
  • Data traffic are often in bursts i.e. Long time no data and short time high data.
    Thus, users do not use their allocated channel capacity most of the channels will be idle most of the time.

Question 43

Describe Dynamic Channel Allocations.

Answer 43

• In this method, no user is assigned fixed frequency or fixed time slot.
  All users are dynamically assigned frequency or time slot, depending upon the requirements of the user.

Question 44

Describe pure ALOHA.

Answer 44

• Stations can transmit frames whenever they have data to send.
  
  • However, collisions can occur
    ○ When two stations transmit simultaneously, there is collision and frames are lost.
    ○ Whenever two frames try to occupy the channel at the same time, there will be a collision and both the frames will be lost.
    If first bit of a new frame overlaps with the last bit of a frame, both frames will be lost and both will have to be retransmitted.

Question 45

Describe slotted Aloha.

Answer 45

• In slotted Aloha, the time is divided to frame-size slots.
  
  • The station can send a frame only a the beginning of the slot and only one frame is sent in each slot.
  • If any station is not able to place the frame onto the channel at the beginning of the slot, it has to wait until the next time slot.
    There is still a possibility of collision if two stations try to send at the beginning of the same time slot.

Question 46

Describe the differences between 1-persistent, non-persistent and p-persistent CSMA.

Answer 46

• 1-persistent CSMA
  ○ When a station has data to send, it first listens to the channel to see if anyone else is transmitting at that moment.
  ○ If channel is idle, then the station sends their data.
  ○ Otherwise, if the channel is busy, the station just waits until it becomes idle.
  ○ The station transmits a frame - if collision occurs, the station waits a random amount of time and starts all over again. The protocol is called 1-persistent because the station transmits with a probability of 1 when it finds the channel idle.
  • Non-persistent CSMA
    ○ Similar to 1-persistent but less greedy. It does not keeping sensing whether the channel is idle, it does it once if busy then it will wait for a random amount of time and then repeats the algorithm.
    ○ This leads to better channel utilization but longer delays than 1-persistent CSMA.
  • P-persistent CSMA
    ○ If station is idle it transmits frame with probability p. With probability q = 1 - p, it defers until the next slot.
    ○ If that slot is also idle, it either transmits or defers again, with probabilities p and q.
    ○ This process is repeated until either frame has been transmitted or another station has begun transmitting.
    ○ In the latter case, the unlucky station acts as if there had been a collision (i.e. Waits a random amount of time and starts again).
    ○ If the station initially states that the channel is busy, it waits until the next slot and applies the above algorithm.

Question 47

Explain CSMA with Collison Detection and what it aims to improve.

Answer 47

• If two stations sense the channel to be idle and begin transmitting simultaneously, their signals will collide.
  
  • If a collision is detected, the station aborts its transmission and waits for a random amount of time & sends its data again.
  • As soon as a collision is detected, the transmitting station release a jam signal.
  • Jam signal alerts other stations. Stations are not supposed to transmit immediately after the collision has occurred.

Question 48

Describe the Bit-Map Protocol (a type of reservation protocol).

Answer 48

• Each contention period consists of exactly N slots.
  
  • If a station k has a frame to send, it transmits a 1 bit during slot k. No other station is allowed to transmit during this slot.
  • After all N slots have passed by each station has complete knowledge of which stations wish to transmit.
  • At that point, they begin transmitting frames in numerical order. Since everyone agrees on who goes next, there will never be any collisions.
  • After the last ready station has transmitted its frame, an event all stations can easily monitor, another N-bit contention period is begun. If station becomes ready just after its bit slot has passed by, it is out of luck and must remain silent until every station has had a chance and the bit map has come round again.
    This is a type of reservation protocol because they reserve channel ownership in advance and prevent collisions.

Question 49

Describe Token Passing.

Answer 49

• Similar to Bit-Map protocol (reservation) but done differently .. Lets every station transmit a frame in turn in a predefined order.
  
  • Pass a small message called a token from one station to the next in the same predefined order.
  • The token represents permission to send.
  • If a station has a frame queued for transmission when it receives the token, it can send that frame before it passes the token to the next station. (if it has no queued frame it simply passes the token)
  • Frames are also transmitted in the direction of the token. Thus way they will circulate around the ring and reach whichever station is the destination.
    ○ But to stop the frame from circulating indefinitely, some stations needs to remove it from the ring.
    This station may be either the one that originally sent the frame, after it has gone through a complete cycle, or the station that was the intended recipient of the frame.

Question 50

Describe Binary Countdown.

Answer 50

• Aims to resolve the problem that token passing has an overhead of 1 bit per station, so it does not scale well to networks with thousands of stations.
  
  • A station wanting to use the channel now broadcasts its address as a binary bit string, starting with the high order bit.
  • All addresses are assumed to be the same length. The bits in each address position from different stations are BOOLEAN Ores together by the channel when they are sent at the same time.
  • To avoid conflicts, an arbitration rule must be applied: as soon as a station sees that a higher-order bit position that is 0 in its address has been overwritten with a 1, it gives up. For example, if stations 0010, 0100, 1001, and 1010 are all trying to get the channel, in the first bit time the stations transmit 0, 0, 1, and 1 respectively.
  • These are OR read together to form a 1. Stations 0010 and 0100 see the 1 and know that a higher numbered station is competing for the channel, so they give up for the current round. Stations 1001 and 1010 continue.
  • The next bit is 1, so station 1001 gives up.
  • The winner station 1010 because it has the highest address..
  • After winning the bidding, it may now transmit a frame, after which another bidding cycle starts.
    This protocol may be good or bad - depending on the context.

Question 51

Describe Byte Count.

Answer 51

• Uses a field in the header to specify the number of bytes in the frame.
  
  • When the datalink layer at the destination sees the byte count it knows how many bytes follow hence where the end of the frame is.
  • The problem with this method is that the count can be garbled by a transmission error.
    ○ E.g. If the byte count of 5 in the second frame of Fig. 3(b) becomes 7 due to signal bit flip, the destination will get out of synchronisation.
    It will then be unable to locate the correct start of the next frame.

Question 52

Describe Flag Byte.

Answer 52

• Two consecutive flag bytes indicate the end of one frame and the start of the next.
  
  • Thus, if the receiver ever loses synchronization it can just search for two flag bytes to find the end of the current frame and start of the next frame.
  • However, a problem still lies -> It may happen that the flag byte occurs in the data.
  • This situation would interfere with the framing -> one way to solve this problem is to have the sender’s data link layer insert a special escape byte (ESC) just before each “accidental” flag byte in the data.
  • Thus, a framing flag byte can be distinguished from one in the data by the absence or presence of an escape byte before it.
    The data link layer on the receiving end removes the escape bytes before giving the data to the network layer.

Question 53

What is Bit stuffing?

Answer 53

• Each frame begins and ends with a special bit pattern 01111110 or 0x7E in hexadecimal. This pattern is a flag byte. Whenever the sender’s data link layer encounters five consecutive 1s in the data it automatically stuffs a 0 bit into the outgoing bit stream.
  
  • This bit stuffing is analogous to byte stuffing, in which an escape byte is stuffed into the outgoing character stream before a flag byte in the data.
  • When the receiver sees five consecutive incoming 1 bits, followed by a 0 bit, it automatically deletes the 0 bit.
    If the user data contains the flag pattern, 01111110, this flag is transmitted as 011111010 but stored in the receiver’s memory as 01111110.

Question 54

Hamming Codes

Answer 54

• Codes add redundancy to the information that is sent.
  
  • A frame consists of m data (i.e., message) bits and r redundant (i.e. Check) bits.
  • Let the total block be n (i..e. n = m + r)
  • We will describe this as an (n,m) code
  • An n-bit unit containing data and check bits is referred to as an n-bit codeword.
  • Two determine how many bits differ between two code words we just XOR the two and count the number of 1 bits in the result.
    ○ The number of bit positions in which two codewords differ is called the Hamming distance
    ○ It’s significance is that if two codewords are a Hamming distance d apart, it will require d single-bit errors to convert one into the other.

Take the example, consider a code with only four valid codewords: 0000000000, 0000011111, 1111100000, 1111111111. This code has a distance of 5, which means that it can correct double errors or detect quadruple errors.

	○ If the codeword 0000000111 arrived we expect only single- or double bit errors, the receiver will know that the original must have been 0000011111.
	○ However if a triple error occurs, the error will not be corrected properly.

Check bits reside in positions that are powers of 2 (1, 2, 4, 8, 16, etc). The rest (3, 5, 6, 7, 9 etc) are filled up with the m data bits. (11, 7) Hamming Code with 7 data bits and 4 check bits.

Question 55

Describe parity check

Answer 55

• Simplest form of error detection.
  
  • The sender simply includes one additional bit and chooses its value such that the total number of 1s in the d + 1 bits (the original information plus a parity bit) is even. The same can be applied for odd parity schemes where the total number of 1s is odd.
  • The receiving end need only count the number of 1s in the received d + 1 bits. If an odd number of 1s then it is known that an error has occurred.

With a two dimensional parity bit scheme we can not only detect that there is an error but where the error occurred.

Question 56

Describe Check Sum.

Answer 56

• Sum k-bit integers being passed and use the resulting sum as the error-detection bits.
• The internet checksum is based on this approach - bytes of data are treated as 16-bit integers and summed.
• The 1s complement of this sum then forms the Internet check sum that is carried in the segment header.
• The receiver checks the checksum by taking the 1s complement of the sum of the received data (including the checksum) then compare and check whether the result is all 1 bits. -> Comparing if the checksum remains consistent.
If any of the bits are 0, an error is indicated.

Question 57

Describe cyclic redundancy check.

Answer 57

• Also known as polynomial codes
  
  • E.g, 110001 has 6 bits and thus represents a six-term polynomial with coefficients 1, 1, 0, 0, 0, and 1:
  • 1x^5 + 1x^4 + 0x^3 + 0x^2 + 0x^1 + 1x^0
    Polynomial arithmetic addition and subtraction is the same as XOR:

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

When the polynomial code method is employed, the sender and receiver must agree on a generator polynomial, G(x), in advance.