Chapter 1 Computer Networks and the Internet

• End systems are connected together by a network of communication links and packet switches.

• When one end system has data to send to another end system, the sending end systemsegments the data and adds header bytes to each segment. The resulting packages of information, known as packets.

• the two most prominent types in today’s Internet are routers and link-layer switches

• The sequence of communication links and packet switches traversed by a packet from the sending end system to the receiving end system is known as a route or path through the network.

• ISPs : Internet Service Providers

• Store-and-forward transmission means that the packet switch must receive the entire packet before it can begin to transmit the first bit of the packet onto the outbound link.

• If an arriving packet needs to be transmitted onto a link but finds the link busy with the transmission of another packet, the arriving packet must wait in the output buffer . Thus, in addition to the store-and-forward delays, packets suffer output buffer queuing delays .

• arriving packet may find that the buffer is completely full with other packets waiting for transmission. In this case, packet loss will occur—either the arriving packet or one of the already-queued packets will be dropped.

• a router uses a packet’s destination address to index a forwarding table and determine the appropriate outbound link

• There are two fundamental approaches to moving data through a network of links and switches: circuit switching and packet switching .

• In circuit-switched networks, the resources needed along a path (buffers, link transmission rate) to provide for communication between the end systems are reserved for the duration of the communication session between the end systems.

• A circuit in a link is implemented with either frequency-division multiplexing (FDM) or time-division multiplexing (TDM).

• The most important of these delays are the nodal processing delay , queuing delay , transmission delay , and propagation delay ;

• The time required to examine the packet’s header and determine where to direct the packet is part of the processing delay.

• Transmission Delay:amount of time required to push (that is, transmit) all of the packet’s bits into the link.

• The time required to propagate from the beginning of the link to router B is the propagation delay.

• let a denote the average rate at which packets arrive at the queue (a is in units of packets/sec). Recall that R is the transmission rate; that is, it is the rate (in bits/sec) at which bits are pushed out of the queue. Also suppose, for simplicity, that all packets consist of L bits. Then the average rate at which bits arrive at the queue is La bits/sec. The ratio La/R,is called the traffic intensity.

• If La/R > 1, then the average rate at which bits arrive at the queue exceeds the rate at which the bits can be transmitted from the queue. In this unfortunate situation, the queue will tend to increase without bound and the queuing delay will approach infinity.

• a packet can arrive to find a full queue.With no place to store such a packet, a router will drop that packet; that is, the packet will be lost.

• a lost packet may be retransmitted on an end-to-end basis in order to ensure that all data are eventually transferred from source to destination.

• In VoIP, the sending side must first fill a packet with encoded digitized speech before passing the packet to the Internet. This time to fill a packet—called the packetization delay—can be significant and can impact the user-perceived quality of a VoIP call

• The instantaneous throughput at any instant of time is the rate (in bits/sec) at which client is receiving the file.

• If there are multiple links , the thoroughput is the bottleneck of transmission rate.

• when there is no other intervening traffic, the throughput can simply be approximated as the minimum transmission rate along the path between source and destination.

• The Internet protocol stack consists of five layers: the physical, link, network, transport, and application layers.

• link-layer switches implement layers 1 and 2; routers implement layers 1 through 3.

• DoS attacks fall into one of three categories:

1. Vulnerability attack. This involves sending a few well-crafted messages to a vulnerable application or operating system running on a targeted host. If the right sequence of packets is sent to a vulnerable application or operating system, the service can stop or, worse, the host can crash.
2. Bandwidth flooding. The attacker sends a deluge of packets to the targeted host—so many packets that the target’s access link becomes clogged, preventing legitimate packets from reaching the server.
3. Connection flooding. The attacker establishes a large number of half-open or fully open TCP connections (TCP connections are discussed in Chapter 3) at the target host. The host can become so bogged down with these bogus connections that it stops accepting legitimate connections.

• A passive receiver that records a copy of every packet that flies by is called a packet sniffer.
• The ability to inject packets into the Internet with a false source address is known as IP spoofing, and is but one of many ways in which one user can masquerade as another user.To solve this problem, we will need end-point authentication.

Chapter 2 Application Layer

• two predominant architectural paradigms:the client-server architecture or the peer-to-peer (P2P) architecture.
• A process sends messages into, and receives messages from, the network through a software interface called a socket,also referred to as the Application Programming Interface (API) between the application and the network.
• We can broadly classify the possible services provided by transport-layer protocol along four dimensions: reliable data transfer, throughput, timing,and security.
• When an application invokes TCP as its transport protocol, the application receives both of these services from TCP：Connection-oriented service,Reliable data transfer service, congestion-control mechanism .
• UDP is connectionless, so there is no handshaking before the two processes start to communicate.
• UDP provides an unreliable data transfer service.
• UDP does not include a congestion-control mechanism.

2.1 HTTP

• HTTP is said to be a stateless protocol: server sends requested files to clients without storing any state information about the client.
• Non-Persistent:each request/response pair be sent over a separate TCP connection.
• Persistent Connections:all of the requests and their corresponding responses be sent over the same TCP connection.
• HTTP uses persistent connections in its default mode.
• the steps of transferring a Web page from server to client for the case of non- persistent connections: Let’s suppose the page consists of a base HTML file and 10 JPEG images/computer_networking_topdown, and that all 11 of these objects reside on the same server.Further suppose the URL for the base HTML file is:http://www.someSchool.edu/someDepartment/home.index

Here is what happens:

1. The HTTP client process initiates a TCP connection to the server www.someSchool.edu on port number 80, which is the default port number for HTTP. Associated with the TCP connection, there will be a socket at the client and a socket at the server.
2. The HTTP client sends an HTTP request message to the server via its socket. The request message includes the path name /someDepartment/home .index. (We will discuss HTTP messages in some detail below.)
3. The HTTP server process receives the request message via its socket, retrieves the object from path: /someDepartment/home.index from its storage (RAM or disk), encapsulates the object in an HTTP response message, and sends the response message to the client via its socket.
4. The HTTP server process tells TCP to close the TCP connection. (But TCP doesn’t actually terminate the connection until it knows for sure that the client has received the response message intact.)
5. The HTTP client receives the response message. The TCP connection terminates. The message indicates that the encapsulated object is an HTML file. The client extracts the file from the response message, examines the HTML file, and finds references to the 10 JPEG objects.
6. The first four steps are then repeated for each of the referenced JPEG objects.

• round-trip time (RTT), is the time it takes for a small packet to travel from client to server and then back to the client.

• The RTT includes packet-propagation delays, packet-queuing delays in intermediate routers and switches, and packet-processing delays.(the packet is small so there is no transmission delay)

• Non-persistent connections have some shortcomings.

  1. a brand-new connection must be established and maintained for each requested object. For each of these connections, TCP buffers must be allocated and TCP variables must be kept in both the client and server. This can place a significant burden on the Web server, which may be serving requests from hundreds of different clients simultaneously.
  2. each object suffers a delivery delay of two RTTs—one RTT to establish the TCP connection and one RTT to request and receive an object.

• The first line of an HTTP request message is called the request line,the subsequent lines are called the header lines.

2.1.1 Request Message

• The request line has three fields: the method field, the URL field, and the HTTP version field.

• The method field can take on several different values, including GET, POST,HEAD,PUT,and DELETE

• The header lines:

  1. Host: xxx.xxx.xxx specifies the host on which the object resides.
  2. Connection:close/keep-alive header line tells the server to set the connection to whether persistent or non-persistent.
  3. The User-agent: header line specifies the user agent, that is, the browser type that is making the request to the server.

• after the header lines there is an entity body.The entity body is empty with the GET method, but is used with the POST method.

• HTML form elements often use the GET method and include the inputted data (in the form fields) in the requested URL

• The HEAD method is similar to the GET method. When a server receives a request with the HEAD method, it responds with an HTTP message but it leaves out the requested object.

• The PUT method allows a user to upload an object to a specific path (directory) on a specific Web server.

• The DELETE method allows a user, or an application, to delete an object on a Web server.

2.1.2 Response Message

• HTTP response message has three sections:
  1. Initial status line:The status line has three fields: the protocol version field, a status code, and a corresponding status message.
  2. Header lines:
     • Date: indicates the time and date when the HTTP response was created and sent by the server. Note that this is not the time when the object was created or last modified; it is the time when the server retrieves the object from its file system, inserts the object into the response message, and sends the response message.
     • Content-Type: indicates the type of the object in the entity body.
  3. Entity line.

2.1.3 Cookies

• cookie technology has four components:

  1. a cookie header line in the HTTP response message;
  2. a cookie header line in the HTTP request message;
  3. a cookie file kept on the user’s end system and managed by the user’s browser;
  4. a back-end database at the Web site.

• How the cookies work:

  1. request comes into the Web server, the server creates a unique identification number and creates an entry in its back-end database that is indexed by the identification number. The Web server then responds to client’s browser, including in the HTTP response a Set-cookie: header, which contains the identification number.
  2. When Client’s browser receives the HTTP response message, it sees the Set-cookie: header. The browser then appends a line to the special cookie file that it manages. This line includes the hostname of the server and the identification number in the Set-cookie: header.
  3. As client continues to browse the site, each time he requests a Web page, his browser consults his cookie file,extracts his identification number for this site, and puts a Cookie header line that includes the identification number in the HTTP request.
  4. In this manner, the server is able to track client’s activity at the site.

2.1.4 Web Cache(Proxy)

• A Web cache—also called a proxy server—is a network entity that satisfies HTTP requests on the behalf of an origin Web server.

• A user’s browser can be configured so that all of the user’s HTTP requests are first directed to the Web cache.

• How does web cache work:

  1. The browser establishes a TCP connection to the Web cache and sends an HTTP request for the object to the Web cache.
  2. The Web cache checks to see if it has a copy of the object stored locally:

     1. If it does, the cache performs an up-to-date check by issuing a conditional GET to the web server telling the server to send the object only if the object has been modified since the specified date:

        • If it does then the object is updated.
        • If it doesn’t the object remains the same

        The Web cache returns the object within an HTTP response message to the client browser.

     2. If the Web cache does not have the object, the Web cache opens a TCP connection to the web server, The Web cache then sends an HTTP request for the object into the cache-to-server TCP connection. After receiving this request, the origin server sends the object within an HTTP response to the Web cache.

  3. When the Web cache receives the object, it stores a copy in its local storage and sends a copy, within an HTTP response message, to the client browser (over the existing TCP connection between the client browser and the Web cache).

• The benefits of a web cache:

  1. First, a Web cache can substantially reduce the response time for a client request.
  2. Second, Web caches can substantially reduce traffic on an institution’s access link to the Internet

• HTTP has a mechanism that allows a cache to verify that its objects are up to date. This mechanism is called the conditional GET

2.2 SMTP

• A typical message starts its journey in the sender’s user agent, travels to the sender’s mail server, and travels to the recipient’s mail server, where it is deposited in the recipient’s mailbox.

• How SMTP works:

1. Alice invokes her user agent for e-mail, provides Bob’s e-mail address (for example,bob@someschool.edu), composes a message, and instructs the user agent to send the message.
2. Alice’s user agent sends the message to her mail server, where it is placed in a message queue.
3. The client side of SMTP, running on Alice’s mail server, sees the message in the message queue. It opens a TCP connection to an SMTP server, running on Bob’s mail server.
4. After some initial SMTP handshaking, the SMTP client sends Alice’s message into the TCP connection.
5. At Bob’s mail server, the server side of SMTP receives the message. Bob’s mail server then places the message in Bob’s mailbox.
6. Bob invokes his user agent to read the message at his convenience.

• Five commands in SMTP:

  1. HELO (an abbreviation for HELLO)
  2. MAIL FROM
  3. RCPT TO
  4. DATA
  5. QUIT

• SMTP uses persistent connection.

• MTP requires each message, including the body of each message, to be in 7-bit ASCII format.

• A mail access protocol is used to transfer mail from the recipient’s mail server to the recipient’s user agent.

• There are currently a number of popular mail access protocols, including Post Office Protocol—Version 3 (POP3), Internet Mail Access Protocol (IMAP), and HTTP.

2.3 DNS

• The DNS protocol runs over UDP and uses port 53.

• How DNS works(approximately):

  1. The browser extracts the hostname, from the URL and passes the hostname to the client side of the DNS application.
  2. The DNS client sends a query containing the hostname to a DNS server.
  3. The DNS client eventually receives a reply, which includes the IP address for the hostname.
  4. Once the browser receives the IP address from DNS, it can initiate a TCP connection to the HTTP server process located at port 80 at that IP address

• The desired IP address is often cached in a “nearby” DNS server, which helps to reduce DNS network traffic as well as the average DNS delay.

• DNS provides services such as:

  1. Host aliasing
  2. Mail server aliasing
  3. Load distribution

• there are three classes of DNS servers:

  1. root DNS servers
  2. top-level domain (TLD) DNS servers
  3. authoritative DNS servers

• How DNS works(in detail):

  1. The client first contacts one of the root servers,which returns IP addresses for TLD servers for the top-level domain com.
  2. The client then contacts one of these TLD servers, which returns the IP address of an authoritative server for amazon.com.
  3. Finally,the client contacts one of the authoritative servers for amazon.com, which returns the IP address for the hostname www.amazon.com.

• 2 query methods in DNS:recursive queries and iterative queries

• Typically,The query from the requesting host to the local DNS server is recursive, and the remaining queries are iterative.

• The DNS servers that together implement the DNS distributed database store resource records (RRs)

• A resource record is a four-tuple that contains the following fields:

  1. Name
  2. Value
  3. Type
  4. TTL

• TTL is the time to live of the resource record; it determines when a resource should be removed from a cache.

• If Type=A, then Name is a hostname and Value is the IP address for the hostname.

• If Type=NS, then Name is a domain (such as foo.com) and Value is the hostname of an authoritative DNS server that knows how to obtain the IP addresses for hosts in the domain.

• If Type=CNAME, then Value is a canonical hostname for the alias hostname Name.

• If Type=MX, then Value is the canonical name of a mail server that has an alias hostname Name.

2.4 Video Streaming

• A video is a sequence of images, typically being displayed at a constant rate, for example, at 24 or 30 images.

• the network must provide an average throughput to the streaming application that is at least as large as the bit rate of the compressed video.

• In HTTP streaming, the video is simply stored at an HTTP server as an ordinary file with a specific URL.

• How HTTP streaming works:

  1. When a user wants to see the video, the client establishes a TCP connection with the server and issues an HTTP GET request for that URL.
  2. The server then sends the video file, within an HTTP response message.
  3. On the client side, the bytes are collected in a client application buffer.
  4. Once the number of bytes in this buffer exceeds a predetermined threshold, the client application begins playback—specifically, the streaming video application periodically grabs video frames from the client application buffer, decompresses the frames, and displays them on the user’s screen.

• Dynamic Adaptive Streaming over HTTP(DASH):The client dynamically requests chunks of video segments of a few seconds in length. When the amount of available bandwidth is high, the client naturally selects chunks from a high-rate version; and when the available bandwidth is low, it naturally selects from a low-rate version.

2.5 Content Distribution Networks

• A CDN manages servers in multiple geographically distributed locations, stores copies of content in its servers, and attempts to direct each user request to a CDN location that will provide the best user experience.

• How CDN works:

  1. The user’s host sends a DNS query for the host name of the requested resource.
  2. The user’s Local DNS Server (LDNS) relays the DNS query to an authoritative DNS server for the hostname, which observes in the hostname that this belongs to CDN. To “hand over” the DNS query to CDN, instead of returning an IP address, the authoritative DNS server returns to the LDNS a hostname in the CDN’s domain.
  3. The user’s LDNS then sends a second query, now for the hostname provided in 2, and CDN’s DNS system eventually returns the IP addresses of a CDN content server to the LDNS.
  4. The LDNS forwards the IP address of the content-serving CDN node to the user’s host.
  5. Once the client receives the IP address for a CDN content server, it establishes a direct TCP connection with the server at that IP address and issues an HTTP GET request for the content.

Chapter 3 Transport layer

• Port number is the identifier of the socket.

• Extending host-to-host delivery to process-to-process delivery is called transport-layer multiplexing and demultiplexing.

• This job of delivering the data in a transport-layer segment to the correct socket is called demultiplexing.

• The job of gathering data chunks at the source host from different sockets,encapsulating each data chunk with header information to create segments, and passing the segments to the network layer is called multiplexing.

• UDP socket is fully identified by a two-tuple consisting of a destination IP address and a destination port number.

• TCP socket is identified by a four-tuple: (source IP address, source port number,destination IP address,destination port number).

3.1 UDP

• Note that with UDP there is no handshaking between sending and receiving transport-layer entities before sending a segment.

• UDP’s advantages over TCP:

  1. Finer application-level control over what data is sent, and when.
  2. No connection establishment.
  3. No connection state.
  4. Small packet header overhead.

• UDP Segment Structure

  1. port numbers allow the destination host to pass the application data to the correct process running on the destination end system (that is, to perform the demultiplexing function).
  2. The length field specifies the number of bytes in the UDP segment (header plus data).
  3. The checksum is used by the receiving host to check whether errors have been introduced into the segment.

• How checksum works

  1. At the sender side,assign the 1s complement(The 1s complement is obtained by converting all the 0s to 1s and converting all the 1s to 0s) of the sum of all the 16-bit words in the segment to the checksum field.
  2. At the receiver, all four 16-bit words are added, including the checksum.
  3. If no errors are introduced into the packet, then clearly the sum at the receiver will be 1111111111111111. If one of the bits is a 0, then we know that errors have been introduced into the pack.

• Although UDP provides error checking, it does not do anything to recover from an error.

3.2 Reliable Data Transfer

• With a reliable data transfer, 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 were sent.

• RDT 1.0

  • FSM

• RDT 2.0

  • Control messages allow the receiver to let the sender know what has been received correctly by sending ACK, and what has been received in error by NAK and thus requires repeating. In a computer network setting, reliable data transfer protocols based on such retransmission are known as ARQ (Automatic Repeat reQuest) protocols.

  • FSM

  • Flaw:the ACK or NAK packet could be corrupted!

• RDT 2.1

  • Fix Measure: The sender simply to resend the current data packet when it receives a garbled ACK or NAK packet. And add a new field to the data packet and have the sender number its data packets by putting a sequence number into this field to check whether or not the received packet is a retransmission.

  • FSM

• RDT 2.2

  • We can accomplish the same effect as a NAK if, instead of sending a NAK, we send an ACK for the last correctly received packet.

  • FSM

• RDT 3.0

  • Suppose now that in addition to corrupting bits, the underlying channel can lose packets as well.Two additional concerns must now be addressed by the protocol: how to detect packet loss and what to do when packet loss occurs.
  • Implementing a time-based retransmission mechanism requires a countdown timer that can interrupt the sender after a given amount of time has expired.
  • FSM

3.2.1 Pipelined Reliable Data Transfer

• Pipelined Reliable Data Transfer:Rather than operate in a stop-and-wait manner, the sender is allowed to send multiple packets without waiting for acknowledgments.

• Pipelining has the following consequences:

  1. The range of sequence numbers must be increased.
  2. The sender and receiver sides of the protocols may have to buffer more than one packet.
  3. The range of sequence numbers needed and the buffering requirements will depend on the manner in which a data transfer protocol responds to lost, corrupted, and overly delayed packets.

3.2.1.1 GBN

• Go-Back-N (GBN): the sender is allowed to transmit multiple packets (when available) without waiting for an acknowledgment, but is constrained to have no more than some maximum allowable number, N, of unacknowledged packets in the pipeline.

1. Sequence numbers in the interval [0, base-1] correspond to packets that have already been transmitted and acknowledged.
2. The interval [base, nextseqnum-1] corresponds to packets that have been sent but not yet acknowledged.
3. Sequence numbers in the interval [nextseqnum , base+N-1] can be used for packets that can be sent immediately, should data arrive from the upper layer.
4. Finally, sequence numbers greater than or equal to base+N cannot be used until the packet with sequence number base has been acknowledged.

• the range of permissible sequence numbers for transmitted but not yet acknowledged packets can be viewed as a window of size N over the range of sequence numbers.

3.2.1.2 Selective Repeat

• As the name suggests, selective-repeat protocols avoid unnecessary retransmissions by having the sender retransmit only those packets that it suspects were received in error (that is, were lost or corrupted) at the receiver.

• The SR receiver will acknowledge a correctly received packet whether or not it is in order. Out-of-order packets are buffered until all packets with lower sequence numbers are received, at which point a batch of packets can be delivered in order to the upper layer.

  • How Selective Repeat Works
    • Sender
      1. Data received from above.When data is received from above, the SR sender checks the next available sequence number for the packet. If the sequence number is within the sender’s window, the data is packetized and sent; other-wise it is either buffered or returned to the upper layer for later transmission,as in GBN.
      2. Timeout.Timers are again used to protect against lost packets. However, each packet must now have its own logical timer, since only a single packet will be transmitted on timeout.
      3. ACK received.If an ACK is received, the SR sender marks that packet as having been received, provided it is in the window. If the packet’s sequencenumber is equal to send_base, the window base is moved forward to the unacknowledged packet with the smallest sequence number. If the window moves and there are untransmitted packets with sequence numbers that now fall within the window, these packets are transmitted.
    • Receiver
      1. Packet with sequence number in [rcv_base, rcvbase+N-1 ] is correctly received.In this case, the received packet falls within the receiver’s window and a selective ACK packet is returned to the sender. If there are previous packets not received, the packet in the middle is buffered. If this packet has a sequence number equal to the base of the receive window , then this packet,and any previously buffered and consecutively numbered packets are delivered to the upper layer. The receive window is then moved forward by the number of packets delivered to the upper layer.
      2. Packet with sequence number in [rcv_base-N, rcv_base-1] is correctly received.In this case, an ACK must be generated, even though this is apacket that the receiver has previously acknowledged
      3. Otherwise. Ignore the packet.

• window size must be less than or equal to half the size of the sequence number space for SR protocols.

3.3 TCP

• TCP is said to be connection-oriented because before one application process can begin to send data to another, the two processes must first “handshake” with each other—that is, they must send some preliminary segments to each other to establish the parameters of the ensuing data transfer.

• The TCP “connection” is not an end-to-end TDM or FDM circuit as in a circuit-switched network. Instead,the “connection” is a logical one, with common state residing only in the TCPs in the two communicating end systems.

• A TCP connection provides a full-duplex service: If there is a TCP connection between Process A on one host and Process B on another host, then application-layer data can flow from Process A to Process B at the same time as application-layer data flows from Process B to Process A.

• A TCP connection is also always point-to-point, that is, between a single sender and a single receiver. So-called “multicasting”—the transfer of data from one sender to many receivers in a single send operation—is not possible with TCP.

• The maximum amount of data that can be grabbed and placed in a segment is limited by the maximum segment size (MSS).

• The MSS is typically set by first determining the length of the largest link-layer frame that can be sent by the local sending host (the so-called maximum transmission unit, MTU), and then setting the MSS to ensure that a TCP segment(when encapsulated in an IP datagram) plus the TCP/IP header length (typically 40 bytes) will fit into a single link-layer frame.

• Note that the MSS is the maximum amount of application-layer data in the segment, not the maximum size of the TCP segment including headers.

• a TCP connection consists of buffers, variables, and a socket connection to a process in two hosts of a connection pair.

• The TCP segment consists of header fields and a data field.

• When TCP sends a large file, such as an image as part of a Web page, it typically breaks the file into chunks of size MSS (except for the last chunk, which will often be less than the MSS).

• The Structure Of The TCP Segment

  

  1. the header includes source and destination port numbers.
  2. the header includes a checksum field
  3. The 32-bit sequence number field and the 32-bit acknowledgment number field are used by the TCP sender and receiver in implementing a reliable data transfer service.
  4. The 16-bit receive window field is used for flow control.
  5. The 4-bit header length field specifies the length of the TCP header in 32-bit words.
  6. The optional and variable-length options field is used when a sender and receiver negotiate the maximum segment size (MSS) or as a window scaling factor for use in high-speed networks. A time-stamping option is also defined.
  7. The flag field contains 6 bits:
  8. The ACK bit is used to indicate that the value carried in the acknowledgment field is valid.
  9. The RST,SYN, and FIN bits are used for connection setup and teardown.
  10. The CWR and ECE bits are used in explicit congestion notification.
  11. Setting the PSH bit indicates that the receiver should pass the data to the upper layer immediately.
  12. the URG bit is used to indicate that there is data in this segment that the sending-side upper-layer entity has marked as “urgent.”The location of the last byte of this urgent data is indicated by the 16-bit urgent data pointer field

• The sequence number for a segment is the byte-stream number of the first byte in the segment.

• The acknowledgment number that a host puts in its segment is the sequence number of the next byte the host is expecting from its peer host.

• TCP only acknowledges bytes up to the first missing byte in the stream, TCP is said to provide cumulative acknowledgments.

• when a host receives out-of-order segments in a TCP connection,it keeps the out-of-order bytes and waits for the missing bytes to fill in the gaps.

• In practice, both sides of a TCP connection randomly choose an initial sequence number.This is done to minimize 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 later connection between these same two hosts (which also happen to be using the same port numbers as the old connection)

• Telnet : A Case Study for Sequence and Acknowledgment Numbers

• most TCP implementations take only one Sample RTT measurement at a time.That is, at any point in time, the SampleRTT is being estimated for only one of the transmitted but currently unacknowledged segments, leading to a new value of SampleRTT approximately once every RTT.

• TCP updates EstimatedRTT according to the following formula:EstimatedRTT=(1−α)⋅EstimatedRTT+α⋅SampleRTT

• DevRTT, as an estimate of how much SampleRTT typically deviates from Estimated RTT:DevRTT=(1−β)⋅DevRTT+β⋅|SampleRTT−EstimatedRTT|

• How to compute timeout interval:

  1. An initial TimeoutInterval value of 1 second is recommended [RFC 6298].
  2. When a timeout occurs, the value of TimeoutInterval is doubled.
  3. As soon as a segment is received and EstimatedRTT is updated, the TimeoutInterval is computed using the formula:TimeoutInterval=EstimatedRTT+4⋅DevRTT

• the recommended TCP timer management procedures [RFC 6298] use only a single retransmission timer, even if there are multiple transmitted but not yet acknowledged segments

3.3.1 TCP Reliable Data Transfer

• Highly Simplified Description

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// Assume sender is not constrained by TCP flow or congestion control,that data from above is less than MSS in size, and that data transfer is in one direction only. 
NextseqNum=InitialseqNumber
sendBase=InitialseqNumber
loop (forever) {
  switch(event)
    event: data received from application above
      create TCP segment with sequence number NextSegNum
      if ( timer currently not running)
        start timer
      pass segment to IP
      NextseqNum=NextseqNum+length (data)
      break;
    event: timer timeout
      retransmit not-yet-acknowledged segment with smallest sequence number
      start timer
      timer*=2
      break;
    event: ACK received, with ACK field value of y
            if (y > SendBase) {
              SendBase=y
              if (there are currently any not yet acknowledged segments)
                 start timer
            }
            else {/* a duplicate ACK for already ACKed segment */
               increment number of duplicate ACKs received for y
               if (number of duplicate ACKS received for y==3)
                   /* TCP fast retransmit */
                   resend segment with sequence number y
            }
           break;

• TCP ACK Generation Recommendation

• Fast Retransmit:If the TCP sender receives three duplicate ACKs for the same data, it takes this as an indication that the segment following the segment that has been ACKed three times has been lost.the TCP sender performs a fast retransmit , retransmitting the missing segment before that segment’s timer expires.

• TCP’s error-recovery mechanism is probably best categorized as a hybrid of GBN and SR protocols.

3.3.2 TCP Flow Control

• If the application is relatively slow at reading the data, the sender can very easily overflow the connection’s receive buffer by sending too much data too quickly.

• TCP provides a flow-control service to its applications to eliminate the possibility of the sender overflowing the receiver’s buffer.

• How TCP Flow Control Works:

  1. Suppose that Host A is sending a large file to Host B over a TCP connection. Host B allocates a receive buffer to this connection; denote its size by $RcvBuffer$. From time to time, the application process in Host B reads from the buffer. Define the following variables:
  • $LastByteRead$: the number of the last byte in the data stream read from the buffer by the application process in B
  • $LastByteRcvd$: the number of the last byte in the data stream that has arrived from the network and has been placed in the receive buffer at B

  2. Because TCP is not permitted to overflow the allocated buffer, we must have: $$ LastByteRcvd−LastByteRead≤RcvBuffer $$

  3. The receive window, denoted $rwnd$ is set to the amount of spare room in the buffer: $$ rwnd=RcvBuffer−[LastByteRcvd−LastByteRead] $$

  4. Host B tells Host A how much spare room it has in the connection buffer by placing its current value of $rwnd$ in the receive window field of every segment it sends to A.

  5. Host A in turn keeps track of two variables, $LastByteSent$ and $LastByteAcked$,$LastByteSent - LastByteAcked$, is the amount of unacknowledged data that A has sent into the connection

  6. Host A makes sure throughout the connection’s life that: $$LastByteSent−LastByteAcked≤rwnd$$

• The TCP specification requires Host A to continue to send segments with one data byte when B’s receive window is zero. These segments will be acknowledged by the receiver. Eventually the buffer will begin to empty and the acknowledgments will contain a nonzero $rwnd$ value.

3.3.3 TCP Three-Way Handshake

• How The Three-way Handshaking Works:
  1. The client-side TCP first sends a special TCP segment to the server-side TCP. This special segment contains no application-layer data. But one of the flag bits in the segment’s header , the SYN bit, is set to 1. For this reason, this special segment is referred to as a SYN segment. In addition, the client randomly chooses an initial sequence number ($client_isn$) and puts this number in the sequence number field of the initial TCP SYN segment. This segment is encapsulated within an IP datagram and sent to the server.
  2. Once the IP datagram containing the TCP SYN segment arrives at the server host (assuming it does arrive!), the server extracts the TCP SYN segment from the datagram, allocates the TCP buffers and variables to the connection, and sends a connection-granted segment to the client TCP.The connection-granted segment is referred to as a SYNACK segment.This connection-granted segment also contains no application-layer data. However, it does contain three important pieces of information in the segment header:
     • the SYN bit is set to 1.
     • the acknowledgment field of the TCP segment header is set to $client_isn+1$
     • the server chooses its own initial sequence number (server_isn) and puts this value in the sequence number field of the TCP segment header
  3. Upon receiving the SYNACK segment, the client also allocates buffers and variables to the connection. The client host then sends the server yet another segment; this last segment acknowledges the server’s connection-granted segment (the client does so by putting the value server_isn+1 in the acknowledgment field of the TCP segment header). The SYN bit is set to zero, since the connection is established. This third stage of the three-way handshake may carry client-to-server data in the segment payload.

3.3.4 TCP Closing

1. The client application process issues a close command. This causes the client TCP to send a special TCP segment to the server process. This special segment has a flag bit in the segment’s header, the FIN bit , set to 1.
2. When the server receives this segment, it sends the client an acknowledgment segment in return. The server then sends its own shutdown segment, which has the FIN bit set to 1.
3. Finally, the client acknowledges the server’s shutdown segment. At this point, all the resources in the two hosts are now deallocated.

• TCP States

• RST Segment:suppose a host receives a TCP SYN packet with destination port which it is not accepting connections on . Then the host will send a special reset segment to the source. This TCP segment has the RST flag bit set to 1.

3.3.5 TCP Congestion Control

• Costs of Congestion:

  1. large queuing delays are experienced as the packet-arrival rate nears the link capacity.
  2. the sender must perform retransmissions in order to compensate for dropped (lost) packets due to buffer overflow.
  3. a router to use its link bandwidth to forward unneeded copies of a packet.
  4. 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.

• Approaches to Congestion Control:

  1. End-to-end congestion control
  2. Network-assisted congestion control

• The TCP congestion-control mechanism operating at the sender keeps track of an additional variable, the congestion window,denoted $cwnd$.

• At the beginning of every RTT, the constraint permits the sender to send $cwnd$ bytes of data into the connection; at the end of the RTT the sender receives acknowledgments for the data. Thus the sender’s send rate is roughly $cwnd/RTT \ bytes/sec$.

• How TCP Sender Determines Sending Rate

  1. A lost segment implies congestion, and hence, the TCP sender’s rate should be decreased when a segment is lost.
  2. An acknowledged segment indicates that the network is delivering the sender’s segments to the receiver, and hence, the sender’s rate can be increased when an ACK arrives for a previously unacknowledged segment.

• TCP congestion-control algorithm consists of 3 components:

1. Slow Start
2. Congestion avoidance
3. fast recovery

• Slow Start

1. The value of cwnd begins at 1 MSS and increases by 1 MSS every time a transmitted segment is first acknowledged.This process results in a doubling of the sending rate every RTT.
2. If there is a loss event (i.e., congestion) indicated by a timeout, the TCP sender sets the value of cwnd to 1 and begins the slow start process anew. It also sets the value of ssthresh (shorthand for “slow start threshold”) to cwnd/2—half of the value of the congestion window value when congestion was detected.
3. Thus, when the value of cwnd equals ssthresh, slow start ends and TCP transitions into congestion avoidance mode.
4. if three duplicate ACKs are detected, in which case TCP performs a fast retransmit and enters the fast recovery state

• Congestion Avoidance

  1. TCP adopts a more conservative approach and increases the value of cwnd by just a single MSS every RTT.
  2. When a timeout occurs. The value of cwnd is set to 1 MSS, and the value of ssthresh is updated to half the value of cwnd when the loss event occurred.TCP transitions to Slow Start mode.
  3. Triple duplicate ACK:TCP halves the value of cwnd and records the value of ssthresh to be half the value of cwnd (adding in 3 MSS for good measure to account for the triple duplicate ACKs received). The fast-recovery state is then entered.

• Fast Recovery

  1. The value of cwnd is increased by 1 MSS for every duplicate ACK received for the missing segment that caused TCP to enter the fast-recovery state.
  2. when an ACK arrives for the missing segment, TCP enters the congestion-avoidance state after deflating $cwnd$.
  3. If a timeout event occurs, fast recovery transitions to the slow-start state after performing the same actions as in slow start and congestion avoidance.

• How TCP Congestion Control Provides Fairness

• Explicit Congestion Notification (ECN): Network-assisted Congestion Control:At the network layer, two bits (with four possible values, overall) in the Type of Service field of the IP datagram header are used for ECN:
  1. One setting of the ECN bits-ECE (Explicit Congestion Notification Echo) bit is used by a router to indicate that it (the router) is experiencing congestion. This congestion indication is then carried in the marked IP datagram to the destination host, which then informs the sending host.
  2. A second setting of the ECN bits is used by the sending host to inform routers that the sender and receiver are ECN-capable

Chapter 4 Network Layer

• Forwarding refers to the router-local action of transferring a packet from an input link interface to the appropriate output link interface. Forwarding takes place at very short timescales (typically a few nanoseconds), and thus is typically implemented in hardware.
• Routing refers to the network-wide process that determines the end-to-end paths that packets take from source to destination. Routing takes place on much longer timescales (typically seconds), and as we will see is often implemented in software.
• A router forwards a packet by examining the value of one or more fields in the arriving packet’s header, and then using these header values to index into its forwarding table. The value stored in the forwarding table entry for those values indicates the outgoing link interface at that router to which that packet is to be forwarded.

• Best-effort Service:With best-effort service, packets are neither guaranteed to be received in the order in which they were sent, nor is their eventual delivery even guaranteed. There is no guarantee on the end-to-end delay nor is there a minimal bandwidth guarantee.

4.1 Router Architecture

• Input ports. An input port performs several key functions:

  1. It performs the physical layer function of terminating an incoming physical link at a router; this is shown in the leftmost box of an input port and the rightmost box of an output port .
  2. An input port also performs link-layer functions needed to interoperate with the link layer at the other side of the incoming link; this is represented by the middle boxes in the input and output ports.
  3. Perhaps most crucially, a lookup function is also performed at the input port; this will occur in the rightmost box of the input port. It is here that the forwarding table is consulted.

• Switching fabric: The switching fabric connects the router’s input ports to its output ports.

• Output ports: An output port stores packets received from the switching fabric and transmits these packets on the outgoing link by performing the necessary link-layer and physical-layer functions.When a link is bidirectional (that is, carries traffic in both directions), an output port will typically be paired with the input port for that link on the same line card.

• Routing processor. The routing processor performs control-plane functions. In traditional routers, it executes the routing protocols, maintains routing tables and attached link state information, and computes the forwarding table for the router. In SDN routers, the routing processor is responsible for communicating with the remote controller in order to (among other activities) receive forwarding table entries computed by the remote controller, and install these entries in the router’s input ports. The routing processor also performs the network management functions.

• A router’s input ports, output ports, and switching fabric are almost always implemented in hardware

• While the data plane operates at the nanosecond time scale, a router’s control functions。operate at the millisecond or second timescale.

• 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 the longest prefix match.

• Switching Methods:

  1. Switching via memory:The simplest, earliest routers were traditional computers, with switching between input and output ports being done under direct control of the CPU (routing processor).

  2. Switching via a bus:The input port pre-pend a switch-internal label (header) to the packet indicating the local output port to which this packet is being transferred and transmitting the packet onto the bus. All output ports receive the packet, but only the port that matches the label will keep the packet.

  3. One way to overcome the bandwidth limitation of a single, shared bus is to use a more sophisticated interconnection network.A crossbar switch is an interconnection network consisting of 2N buses that connect N input ports to N output ports. Each vertical bus intersects each horizontal bus at a crosspoint, which can be opened or closed at any time by the switch fabric controller (whose logic is part of the switching fabric itself).

• Packet Scheduling

  1. First-in-First-Out (FIFO)
  2. Priority Queuing: packets arriving at the output link are classified into priority classes upon arrival at the queue.When choosing a packet to transmit, the priority queuing discipline will transmit a packet from the highest priority class that has a nonempty queue (that is, has packets waiting for transmission). The choice among packets in the same priority class is typically done in a FIFO manner.Under a non-preemptive priority queuing discipline, the transmission of a packet is not interrupted once it has begun.
  3. Round Robin:Under the round robin queuing discipline, packets are sorted into classes as with priority queuing. However, rather than there being a strict service priority among classes, a round robin scheduler alternates service among the classes.
  4. A generalized form of round robin queuing that has been widely implemented in routers is the so-called weighted fair queuing (WFQ) discipline.during any interval of time during which there are class i packets to send, class i will then be guaranteed to receive a fraction of service equal to $w_i/(∑w_j)$ where the sum in the denominator is taken over all classes that also have packets queued for transmission.

4.2 The Internet Protocol (IP)

4.2.1 IPv4

4.2.1.1 IPv4 Datagram Structure

1. Version number
2. Header length:these 4 bits are needed to determine where in the IP datagram the payload actually begins
3. Type of service: The type of service (TOS) bits were included in the IPv4 header to allow different types of IP datagrams to be distinguished from each other
4. Datagram length. This is the total length of the IP datagram (header plus data), measured in bytes.
5. Identifier, flags, fragmentation offset
6. Time-to-live:This field is decremented by one each time the datagram is processed by a router. If the TTL field reaches 0, a router must drop that datagram.
7. Protocol:The value of this field indicates the specific transport-layer protocol to which the data portion of this IP datagram should be passed.
8. Header Checksum:The header checksum is computed by treating each 2 bytes in the header as a number and summing these numbers using 1s complement arithmetic.
9. Source and destination IP addresses
10. Options
11. Data (payload):In most circumstances, the data field of the IP datagram contains the transport-layer segment (TCP or UDP) to be delivered to the destination. However, the data field can carry other types of data, such as ICMP messages

4.2.1.2 Fragment

• The maximum amount of data that a link-layer frame can carry is called the maximum transmission unit (MTU)
• each of the links along the route between sender and destination can use different link-layer protocols, and each of these protocols can have different MTUs
• When Does Fragment Occur:When outgoing link has an MTU that is smaller than the length of the IP datagram,the payload in the IP datagram is fragmented into two or more smaller IP datagrams,and encapsulated in a separate link-layer frame
• Fragments Reassembly:When a destination host receives a series of datagrams from the same source,it needs to determine whether any of these datagrams are fragments of some original, larger datagram.If some datagrams are fragments, it must further determine when it has received the last fragment and how the fragments it has received should be pieced back together to form the original datagram:
  1. When a datagram is created, the sending host stamps the datagram with an identification number as well as source and destination addresses.
  2. When a router needs to fragment a datagram, each resulting datagram (that is, fragment) is stamped with the source address, destination address, and identification number of the original datagram.
  3. When the destination receives a series of datagrams from the same sending host, it can examine the identification numbers of the datagrams to determine which of the datagrams are actually fragments of the same larger datagram.
  4. In order for the destination host to be absolutely sure it has received the last fragment of he original datagram, the last fragment has a flag bit set to 0, whereas all the other fragments have this flag bit set to 1.
  5. In order for the destination host to determine whether a fragment is missing (and also to be able to reassemble the fragments in their proper order), the offset field is used to specify where the fragment fits within the original IP datagram.

4.2.1.3 Addressing

• The boundary between the host or router and the physical link is called an interface

• An IP address is technically associated with an interface, rather than with the host or router containing that interface

• In IP terms, the network interconnecting host interfaces and router interface forms a subnet.

• subnet mask:/n indicates that the leftmost n bits of the 32-bit quantity define the subnet address.

• Classless Interdomain Routing (CIDR) strategy:The x most significant bits of an address of the form a.b.c.d/x constitute the network portion of the IP address, and are often referred to as the prefix (or network prefix) of the address.only these x leading prefix bits are considered by routers outside the organization’s network. That is, when a router outside the organization forwards a datagram whose destination address is inside the organization, only the leading x bits of the address need be considered.The remaining 32-x bits of an address can be thought of as distinguishing among the devices within the organization.

• For DHCP protocol to work,each subnet will have a DHCP server. If no server is present on the subnet, a DHCP relay agent (typically a router) that knows the address of a DHCP server for that network is needed.

• DHCP protocol is a four-step process:

  

  1. DHCP server discovery: A newly arriving host sends within a UDP packet to port 67. the DHCP client creates an IP datagram containing its DHCP discover message along with the broadcast destination IP address of 255.255.255.255 and a “this host” source IP address of 0.0.0.0. The DHCP client passes the IP datagram to the link layer, which then broadcasts this frame to all nodes attached to the subnet
  2. DHCP server offer(s). A DHCP server receiving a DHCP discover message responds to the client with a DHCP offer message that is broadcast to all nodes on the subnet , again using the IP broadcast address of 255.255.255.255.Each server offer message contains the transaction ID of the received discover message, the proposed IP address for the client, the network mask, and an IP address lease time.
  3. DHCP request. The newly arriving client will choose from among one or more server offers and respond to its selected offer with a DHCP request message, echoing back the configuration parameters
  4. DHCP ACK. The server responds to the DHCP request message with a DHCP ACK message, confirming the requested parameters

• A realm with private addresses refers to a network whose addresses only have meaning to devices within that network.

• The NAT router behaves to the outside world as a single device with a single IP address.

• The router gets its address from the ISP’s DHCP server, and the router runs a DHCP server itself to provide addresses to computers within the NAT-DHCP-router- controlled home network’s address space.
• All datagrams arriving at the NAT router from the WAN have the same destination IP address , how does the router know the internal host to which it should forward a given datagram?
  1. Suppose a user sitting in a home network behind host 10.0.0.1 requests a Web page on some Web server (port 80) with IP address 128.119.40.186. The host 10.0.0.1 assigns the (arbitrary) source port number 3345 and sends the datagram into the LAN.
  2. The NAT router receives the datagram, generates a new source port number 5001 for the datagram, replaces the source IP address with its WAN-side IP address 138.76.29.7, and replaces the original source port number 3345 with the new source port number 5001.NAT in the router also adds an entry to its NAT translation table.
  3. The Web server responds with a datagram whose destination address is the IP address of the NAT router, and whose destination port number is 5001. When this datagram arrives at the NAT router, the router indexes the NAT translation table using the destination IP address and destination port number to obtain the appropriate IP address (10.0.0.1) and destination port number (3345) for the browser in the home network. The router then rewrites the datagram’s destination address and destination port number, and forwards the datagram into the home network.

4.2.2 IPv6

• IPv6 Important Changes:

  1. Expanded addressing capabilities
  2. A streamlined 40-byte header
  3. Flow labeling

• IPv6 datagram format

1. Version
2. Traffic class: The 8-bit traffic class field, like the TOS field in IPv4, can be used to give priority to certain datagrams within a flow, or it can be used to give priority to datagrams from certain applications (for example, voice-over-IP) over datagrams from other applications (for example, SMTP e-mail).
3. Flow label
4. Payload length
5. Next header. This field identifies the protocol to which the contents (data field) of this datagram will be delivered (for example, to TCP or UDP). The field uses the same values as the protocol field in the IPv4 header.
6. Hop limit: The contents of this field are decremented by one by each router that forwards the datagram. If the hop limit count reaches zero, the datagram is ­discarded.
7. Source and destination addresses
8. Data

• Fields appearing in the IPv4 datagram are no longer present in the IPv6 datagram:

  1. Fragmentation/reassembly:If an IPv6 datagram received by a router is too large to be forwarded over the outgoing link, the router simply drops the datagram and sends a “Packet Too Big” ICMP error message back to the sender. The sender can then resend the data, using a smaller IP datagram size.
  2. Header checksum: Because the transport-layer (for example, TCP and UDP) and link-layer (for example, Ethernet) protocols in the Internet layers perform checksumming, the designers of IP probably felt that this functionality was sufficiently redundant in the network layer that it could be removed.
  3. Options:Instead, the options field is one of the possible next headers pointed to from within the IPv6 header. That is, just as TCP or UDP protocol headers can be the next header within an IP packet, so too can an options field. The removal of the options field results in a fixed-length, 40-byte IP header

• The approach to IPv4-to-IPv6 transition that has been most widely adopted in practice involves tunneling:With tunneling, the IPv6 node on the sending side of the tunnel (in this example, B) takes the entire IPv6 datagram and puts it in the data (payload) field of an IPv4 datagram. This IPv4 datagram is then addressed to the IPv6 node on the receiving side of the tunnel.

• Each entry in the match-plus-action forwarding table, known as a flow table in OpenFlow, includes:

  1. A set of header field values to which an incoming packet will be matched.If a packet matches multiple flow table entries, the selected match and corresponding action will be that of the highest priority entry with which the packet matches.
  2. A set of counters that are updated as packets are matched to flow table entries. These counters might include the number of packets that have been matched by that table entry, and the time since the table entry was last updated.
  3. A set of actions to be taken when a packet matches a flow table entry. These actions might be to forward the packet to a given output port, to drop the packet, makes copies of the packet and sent them to multiple output ports, and/or to rewrite selected header fields.

Chapter 5 The Network Layer: Control Plane

• A centralized routing algorithm computes the least-cost path between a source and destination using complete, global knowledge about the network.Algorithms with global state information are often referred to as link-state (LS) algorithms, since the algorithm must be aware of the cost of each link in the network.

• In a link-state algorithm, the network topology and all link costs are known.In practice this is accomplished by having each node broadcast link-state packets to all other nodes in the network, with each link-state packet containing the identities and costs of its attached links. The result of the nodes’ broadcast is that all nodes have an identical and complete view of the network. Each node can then run the LS algorithm and compute the same set of least-cost paths as every other node

• Popular LS-Algorithm:Dijkstra’s algorithm,Prim’s algorithm

• In a decentralized routing algorithm, the calculation of the least-cost path is carried out in iterative, distributed manner by the routers. 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.The decentralized routing algorithm we’ll study is called a distance-vector (DV) algorithm, because each node maintains a vector of estimates of the costs (distances) to all other nodes in the network

5.1 Distance-Vector Algorithm

• How does DV algorithm work:
  1. each node x maintains the following routing information:
     • For each neighbor v, the cost $c(x, v)$ from x to directly attached neighbor, v.
     • Node x’s distance vector, that is,$D_x=[D_x(y):y \ in \ N]$ , containing x’s estimate of its cost to all destinations, y, in N
     • The distance vectors of each of its neighbors, that is $D_v=[D_v(y):y \ in \ N]$, for each neighbor v of x
  2. Each node sends a copy of its distance vector to each of its neighbors.
  3. When a node x receives a new distance vector from any of its neighbors w, it saves w’s distance vector, and then uses the Bellman-Ford equation to update its own distance vector as follows: $$D_x(y)=minv \left{ c(x,v)+D_v(y) \right} \qquad for \ each \ node \ y \ in \ N$$
  4. 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 distance vectors.
  5. When a node running the DV algorithm detects a change in the link cost from itself to a neighbor , it updates its distance vector and, if there’s a change in the cost of the least-cost path, informs its neighbors of its new distance vector.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

 Initialization:
   for all destinations y in N:
      Dx (y)= c(x, y)/* if y is not a neighbor then c(x, y)= ∞ */
      for each neighbor w
          Dw (y) = ? for all destinations y in N
      for each neighbor w
          send distance vector  Dx  = [Dx (y): y in N] to w

 loop 
    wait  (until I see a link cost change to some neighbor w or
            until I receive a distance vector from some neighbor w)

    for each y in N:
        Dx (y) = min {c(x, v) + Dw (y)}
        update v*y /* the next hop router along the shortest path to y  */

 if Dx(y) changed for any destination y
       send distance vector Dx   = [Dx (y): y in N] to all neighbors

 forever 

5.2 Link-State Algorithm

• autonomous ­systems (ASs):Routers within the same AS all run the same routing algorithm and have information about each other. The routing algorithm ­running within an autonomous system is called an intra-autonomous system routing ­protocol.

• An autonomous system is identified by its globally unique autonomous system number (ASN)

• OSPF is a link-state protocol that uses flooding of link-state information and a Dijkstra’s least-cost path algorithm.

• With OSPF, each router constructs a complete topological map (that is, a graph) of the entire autonomous system. Each router then locally runs Dijkstra’s shortest-path algorithm to determine a shortest-path tree to all subnets, with itself as the root node. Individual link costs are configured by the network administrator.

• With OSPF, a router broadcasts routing information to all other routers in the autonomous system, not just to its neighboring routers. A router broadcasts link-state information whenever there is a change in a link’s state (for example, a change in cost or a change in up/down status). It also broadcasts a link’s state periodically (at least once every 30 minutes), 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. Thus, the OSPF protocol must itself implement functionality such as reliable message transfer and link-state broadcast.

• Some of the advances embodied in OSPF include the following:

  1. Security: Exchanges between OSPF routers (for example, link-state updates) can be authenticated. With authentication, only trusted routers can participate in the OSPF protocol within an AS.
  2. Multiple same-cost paths:When multiple paths to a destination have the same cost, OSPF allows multiple paths to be used
  3. Support for hierarchy within a single AS

5.3 Border Gateway Protocol

• In the Internet, all ASs run the same inter-AS routing protocol, called the Border Gateway Protocol, more commonly known as BGP

• In BGP, packets are not routed to a specific destination address, but instead to CIDRized prefixes, with each prefix representing a subnet or a collection of subnets.

• Thus, a router’s forwarding table will have entries of the form (x, I), where x is a prefix and I is an interface number for one of the router’s interfaces.

• As an inter-AS routing protocol, BGP provides each router a means to:

  1. Obtain prefix reachability information from neighboring ASs. In particular, BGP allows each subnet to advertise its existence to the rest of the Internet.
  2. Determine the “best” routes to the prefixes.

• For each AS, each router is either a gateway router or an internal router.

  1. A gateway router is a router on the edge of an AS that directly connects to one or more routers in other ASs.
  2. An internal router connects only to hosts and routers within its own AS.

• In BGP,pairs of routers exchange routing information over semi-permanent TCP connections using port 179.Each such TCP connection, along with all the BGP messages sent over the connection, is called a BGP connection

• Furthermore, a BGP connection that spans two ASs is called an external BGP (eBGP) connection, and a BGP session between routers in the same AS is called an internal BGP (iBGP) connection.

• In BGP jargon, a prefix along with its attributes is called a route.

• Two of the more important attributes are AS-PATH and NEXT-HOP.

  1. The AS-PATH attribute contains the list of ASs through which the advertisement has passed.To generate the AS-PATH value, when a prefix is passed to an AS, the AS adds its ASN to the existing list in the AS-PATH.BGP routers also use the AS-PATH attribute to detect and prevent looping advertisements; specifically, if a router sees that its own AS is contained in the path list, it will reject the advertisement.
  2. The NEXT-HOP is the IP address of the router interface that begins the AS-PATH.

• Hot Potato Algorithm

• BGP uses an algorithm that is more complicated than hot potato routing, but nevertheless incorporates hot potato routing:

  1. A route is assigned a local preference value as one of its attributes . The local preference of a route could have been set by the router or could have been learned from another router in the same AS. The value of the local preference attribute is a policy decision that is left entirely up to the AS’s network administrator. The routes with the highest local preference values are selected.
  2. From the remaining routes (all with the same highest local preference value), the route with the shortest AS-PATH is selected.
  3. From the remaining routes (all with the same highest local preference value and the same AS-PATH length), hot potato routing is used, that is, the route with the closest NEXT-HOP router is selected.
  4. If more than one route still remains, the router uses BGP identifiers to select the route;

• How Does IP-Anycast Work:

  1. the server-provider assigns the same IP address to each of its servers, and uses standard BGP to advertise this IP address from each of the servers.
  2. When configuring its routing table, each router will locally use the BGP route-selection algorithm to pick the “best” (for example, closest, as determined by AS-hop counts) route to that IP address.
  3. When a client requests the content on the server, it sends request to the common IP address used by the geographically dispersed servers, no matter where the client is located.
  4. Internet routers then forward the request packet to the “closest” server, as defined by the BGP route-selection algorithm.

• IP-anycast is extensively used by the DNS system to direct DNS queries to the closest root DNS server

• How To Prevent multi-homed access ISP from acting as an intermidiate AS:It advertises that it has no paths to any other destinations except itself

5.4 Software Defined Network

• Four key characteristics of an SDN architecture can be identified:

  1. Flow-based forwarding. Packet forwarding by SDN-controlled switches can be based on any number of header field values in the transport-layer, network-layer, or link-layer header.
  2. Separation of data plane and control plane
  3. Network control functions: external to data-plane switches
  4. A programmable network

• the SDN control plane divides broadly into two components—the SDN controller and the SDN network-control applications.

• A controller’s functionality can be broadly organized into three layers:

  1. A communication layer: communicating between the SDN controller and controlled network devices.
  2. A network-wide state-management layer
  3. The interface to the network-control application layer

• The OpenFlow protocol operates over TCP, with a default port number of 6653

• Among the important messages flowing from the controller to the controlled switch are the following:

  • Configuration: This message allows the controller to query and set a switch’s configuration parameters.
  • Modify-State. This message is used by a controller to add/delete or modify entries in the switch’s flow table, and to set switch port properties.
  • Read-State. This message is used by a controller to collect statistics and counter values from the switch’s flow table and ports.
  • Send-Packet. This message is used by the controller to send a specific packet out of a specified port at the controlled switch. The message itself contains the packet to be sent in its payload.

• Among the messages flowing from the SDN-controlled switch to the controller are the following:

  • Flow-Removed: This message informs the controller that a flow table entry has been removed, for example by a timeout or as the result of a received modify-state message.
  • Port-status: This message is used by a switch to inform the controller of a change in port status.
  • Packet-in: A packet arriving at a switch port and not matching any flow table entry is sent to the controller for additional processing. Matched packets may also be sent to the controller, as an action to be taken on a match. The packet-in message is used to send such packets to the controller.

• The SDN has two important differences from the earlier per-router-control scenario , where Dijkstra’s algorithm was implemented in each and every router .Dijkstra’s algorithm is executed as a separate application, outside of the packet switches. Packet switches send link updates to the SDN controller and not to each other.

5.5 Internet Control Message Protocol

• The Internet Control Message Protocol (ICMP), specified in [RFC 792], is used by hosts and routers to communicate network-layer information to each other.

• ICMP messages are carried as IP payload.

• 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 can determine the datagram that caused the error)

5.5.1 Ping

• How Does Ping Program Work:

  1. The well-known ping program sends an ICMP type 8 code 0 message to the specified host.
  2. The destination host, seeing the echo request, sends back a type 0 code 0 ICMP echo reply.

• Most TCP/IP implementations support the ping server directly in the operating system; that is, the server is not a process.

5.5.2 Traceroute

• How Does Traceroute Program Work:
  1. Traceroute in the source sends aseries of ordinary IP datagrams to the destination. Each of these datagrams carries a UDP segment with an unlikely UDP port number. The first of these datagrams has a TTL of 1, the second of 2, the third of 3, and so on. The source also starts timers for each of the datagrams.
  2. When the nth datagram arrives at the nth router, the nth router observes that the TTL of the datagram has just expired. According to the rules of the IP protocol, the router discards the datagram and sends an ICMP warning message to the source (type 11 code 0). This warning message includes the name of the router and its IP address.
  3. When this ICMP message arrives back at the source, the source obtains the round-trip time from the timer and the name and IP address of the nth router from the ICMP message
  4. one of the datagrams will eventually make it all the way to the destination host. Because this datagram contains a UDP segment with an unlikely port number, the destination host sends a port unreachable ICMP message (type 3 code 3) back to the source.
  5. When the source host receives this particular ICMP message, it knows it does not need to send additional probe packets.

5.6 Network Management

• the key components of network management:

1. The managing server is an application, controls the collection, processing, analysis, and/or display of network management information.
2. A managed device is a piece of network equipment (including its software) that resides on a managed network.
3. Each managed object within a managed device associated information that is collected into a Management Information Base (MIB)
4. Also resident in each managed device is a network management agent, a process running in the managed device that communicates with the managing server
5. network ­management protocol

• The Simple Network Management Protocol version 2 (SNMPv2) [RFC 3416] is an application-layer protocol used to convey network-management control and information messages between a managing server and an agent executing on behalf of that managing server.

• SNMPv2 defines seven types of messages, known generically as protocol data units—PDUs:

• the SNMP PDU is preferrably carried in the payload of a UDP datagram

Chapter 6 The Link Layer and LANs

• Any device that runs a link-layer protocol is a node.

• The communication channels that connect adjacent nodes along the communication path are links.

• Possible services that can be offered by a link-layer protocol include:

  1. Framing. Almost all link-layer protocols encapsulate each network-layer datagram within a link-layer frame before transmission over the link. A frame consists of a data field, in which the network-layer datagram is inserted, and a number of header fields. The structure of the frame is specified by the link-layer protocol.
  2. Link access. A medium access control (MAC) protocol specifies the rules by which a frame is transmitted onto the link.
  3. Reliable delivery. When a link-layer protocol provides reliable delivery service, it guarantees to move each network-layer datagram across the link without error. Similar to a transport-layer reliable delivery service, a link-layer reliable delivery service can be achieved with acknowledgments and retransmissions . A link-layer reliable delivery service is often used for links that are prone to high error rates, such as a wireless link, with the goal of correcting an error locally—on the link where the error occurs—rather than forcing an end-to-end retransmission of the data by a transport- or application-layer protocol. However, link-layer reliable delivery can be considered an unnecessary overhead for low bit-error links, including fiber, coax, and many twisted-pair copper links. For this reason, many wired link-layer protocols do not provide a reliable delivery service.
  4. Error detection and correction.This is done by having the transmitting node include error-detection bits in the frame, and having the receiving node perform an error check. Error correction is similar to error detection, except that a receiver not only detects when bit errors have occurred in the frame but also determines exactly where in the frame the errors have occurred (and then corrects these errors)

• Network Adapter:For the most part, the link layer is implemented in a network adapter, also sometimes known as a network interface card (NIC). At the heart of the network adapter is the link-layer controller, usually a single, special-purpose chip that implements many of the link-layer services (framing, link access, error detection, and so on).

• while most of the link layer is implemented in hardware, part of the link layer is implemented in software that runs on the host’s CPU.

  1. On the sending side : The software components of the link layer implement higher-level link-layer functionality such as assembling link-layer addressing information and activating the controller hardware.
  2. On the receiving side, link-layer software responds to controller interrupts (e.g., due to the receipt of one or more frames), handling error conditions and passing a datagram up to the network layer.

• There are two types of network links: point-to-point links and broadcast links.

  1. A point-to-point link consists of a single sender at one end of the link and a single receiver at the other end of the link.
  2. A broadcast link, can have multiple sending and receiving nodes all connected to the same, single, shared broadcast channel.

6.1 Error-Detection and Correction

• At the sending node, data, D, to be protected against bit errors is augmented with error-detection and -correction bits (EDC).Both D and EDC are sent to the receiving node in a link-level frame. At the receiving node, a sequence of bits, D′ and EDC′ is received.The receiver’s challenge is to determine whether or not D′ is the same as the original D, given that it has only received D′ and EDC′.

• The ability of the receiver to both detect and correct errors is known as forward error correction (FEC)

6.1.1 Parity Check

• Suppose that the information to be sent, D , has d bits. In an even parity scheme, the sender simply includes one additional bit and chooses its value such that the total number of 1s in the bits (the original information plus a parity bit) is even. For odd parity schemes, the parity bit value is chosen such that there is an odd number of 1s.

  

• The receiver need only count the number of 1s in the received bits. If an odd number of 1-valued bits are found with an even parity scheme(or vice versa), the receiver knows that at least one bit error has occurred.

6.1.2 Checksum

1. Bytes of data are treated as 16-bit integers and summed. The 1s complement of this sum then forms the Internet checksum that is carried in the segment header.
2. the receiver checks the checksum by taking the the sum of the received data (including the checksum) and checking whether the result is all 1 bits. If any of the bits are 0, an error is indicated.

6.1.3 Cyclic Redundancy Check (CRC)

1. Consider the d-bit piece of data, D, that the sending node wants to send to the receiving node.
2. The sender and receiver must first agree on an bit pattern, known as a generator, which we will denote as G.We will require that the leftmost bit of G be a 1.
3. For a given piece of data, D, the sender will choose r additional bits, R, and append them to D such that the resulting bit pattern is exactly divisible by G (i.e., has no remainder) using modulo-2 arithmetic.The sender calculate R like this:$R=remainder(D/(2^r\times G))$
4. The receiver divides the d+r received bits by G. If the remainder is nonzero, the receiver knows that an error has occurred; otherwise the data is accepted as being correct

6.2 Multiple Access Links

• The multiple access problem:Because all nodes are capable of transmitting frames, more than two nodes can transmit frames at the 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,which are useless.
• 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 is the responsibility of the multiple access protocol.

6.2.1 Channel Partitioning Protocols

6.2.1.1 TDM

TDM divides time into time frames and further divides each time frame into N time slots. Each time slot is then assigned to one of the N nodes. Whenever a node has a packet to send, it transmits the packet’s bits during its assigned time slot in the revolving TDM frame. Typically, slot sizes are chosen so that a single packet can be transmitted during a slot time.

6.2.1.2 FDM

FDM divides the R bps channel into different frequencies (each with a bandwidth of R/N) and assigns each frequency to one of the N nodes. FDM thus creates N smaller channels of R/N bps out of the single, larger R bps channel.

6.2.1.3 Code Division Multiple Access

CDMA assigns a different code to each node. Each node then uses its unique code to encode the data bits it sends.receivers correctly receive a sender’s encoded data bits (assuming the receiver knows the sender’s code)

6.2.2 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 (that is, packet) until its 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.

6.2.2.1 Slotted ALOHA Protocol

• In our description of slotted ALOHA, we assume the following:

  1. All frames consist of exactly L bits.
  2. Time is divided into slots of size L/R seconds (that is, a slot equals the time to transmit one frame).
  3. Nodes start to transmit frames only at the beginnings of slots.
  4. The nodes are synchronized so that each node knows when the slots begin.
  5. If two or more frames collide in a slot, then all the nodes detect the collision event before the slot ends.

• Slotted ALOHA:

  1. When the node has a fresh frame to send, it waits until the beginning of the next slot and transmits the entire frame in the slot.
  2. • If there isn’t a collision, the node has successfully transmitted its frame and thus need not consider retransmitting the frame. (The node can prepare a new frame for transmission, if it has one.)
     • If there is a collision, the node detects the collision before the end of the slot. The node retransmits its frame in each subsequent slot with probability p until the frame is transmitted without a collision.

• Concerns With Slotted ALOHA:

  1. a certain fraction of the slots will have collisions and will therefore be “wasted.”
  2. another fraction of the slots will be empty because all active nodes refrain from transmitting as a result of the probabilistic transmission policy.

6.2.2.2 ALOHA Protocol

1. In pure ALOHA, when a frame first arrives , the node immediately transmits the frame in its entirety into the broadcast channel.
2. If a transmitted frame experiences a collision with one or more other transmissions, the node will then immediately (after completely transmitting its collided frame) retransmit the frame with probability p.
3. 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.

6.2.2.3 Carrier Sense Multiple Access (CSMA)

• Carrier sensing—a node listens to the channel before transmitting. If a frame from another node is currently being transmitted into the channel, a node then waits until it detects no transmissions for a short amount of time and then begins transmission

• Collision detection—a transmitting node listens to the channel while it is transmitting. If it detects that another node is transmitting an interfering frame, it stops transmitting and waits a random amount of time before repeating the sense-and-transmit-when-idle cycle.

• channel propagation delay of a broadcast channel:the time it takes for a signal to propagate from one of the nodes to another.will play a crucial role in determining its performance. The longer this propagation delay, the larger the chance that a carrier-sensing node is not yet able to sense a transmission that has already begun at another node in the network

  

• CSMA/CD from the perspective of an adapter (in a node) attached to a broadcast channel:

  1. The adapter obtains a datagram from the network layer, prepares a link-layer frame, and puts the frame adapter buffer.
  2. If the adapter senses that the channel is idle (that is, there is no signal energy entering the adapter from the channel), it starts to transmit the frame. If, on the other hand, the adapter senses that the channel is busy, it waits until it senses no signal energy and then starts to transmit the frame.
  3. While transmitting, the adapter monitors for the presence of signal energy coming from other adapters using the broadcast channel.
  4. If the adapter transmits the entire frame without detecting signal energy from other adapters, the adapter is finished with the frame. If, on the other hand, the adapter detects signal energy from other adapters while transmitting, it aborts the transmission (that is, it stops transmitting its frame).
  5. After aborting, the adapter waits a random amount of time and then returns to step 2.

• The binary exponential backoff algorithm:when transmitting a frame that has already experienced n collisions, a node chooses the value of K at random from ${ 0,1,2,…2^{n−1} }$,For Ethernet, the actual amount of time a node waits is $K\times the \ amount \ of \ time \ needed \ to \ send \ 512 \ bits \ into \ the \ Ethernet$, the maximum value that n can take is capped at 10

6.2.3 Taking-Turns Protocols

1. polling protocol. The polling protocol requires one of the nodes to be designated as a master node. The master node polls each of the nodes in a round-robin fashion. In particular, the master node first sends a message to node 1, saying that it (node 1) can transmit up to some maximum number of frames. After node 1 transmits some frames, the master node tells node 2 it (node 2) can transmit up to the maximum number of frames. (The master node can determine when a node has finished sending its frames by observing the lack of a signal on the channel.) The procedure continues in this manner, with the master node polling each of the nodes in a cyclic manner.
2. token-passing protocol. In this protocol there is no master node. A small, special-purpose frame known as a token is exchanged among the nodes in some fixed order. For example, node 1 might always send the token to node 2, node 2 might always send the token to node 3, and node N might always send the token to node 1. When a node receives a token, it holds onto the token only if it has some frames to transmit; otherwise, it immediately forwards the token to the next node. If a node does have frames to transmit when it receives the token, it sends up to a maximum number of frames and then forwards the token to the next node.

6.3 Switched Local Area Networks

• In truth, it is not hosts and routers that have link-layer addresses but rather their adapters (that is, network interfaces) that have link-layer addresses.

• link-layer switches do not have link-layer addresses associated with their interfaces that connect to hosts and routers

• A link-layer address is variously called a LAN address, a physical address, or a MAC address.

• For most LANs (including Ethernet and 802.11 wireless LANs), the MAC address is 6 bytes long, giving $2^{48}$ possible MAC addresses.

• One interesting property of MAC addresses is that no two adapters have the same address.

• An adapter’s MAC address has a flat structure (as opposed to a hierarchical structure) and doesn’t change no matter where the adapter goes.

• Sometimes a sending adapter does want all the other adapters on the LAN to receive and process the frame it is about to send. In this case, the sending adapter inserts a special MAC broadcast address into the destination address field of the frame. For LANs that use 6-byte addresses (such as Ethernet and 802.11), the broadcast address is a string of 48 consecutive 1s (that is, FF-FF-FF-FF-FF-FF in hexadecimal notation)

6.3.1 Address Resolution Protocol (ARP)

• Address Resolution Protocol (ARP):translate between network-layer addresses (for example, Internet IP addresses) and link-layer addresses (that is, MAC addresses)

• ARP resolves IP addresses only for hosts and router interfaces on the same subnet.

• Each host and router has an ARP table in its memory, which contains mappings of IP addresses to MAC addresses.

• The ARP table also contains a time-to-live (TTL) value, which indicates when each mapping will be deleted from the table.

• A table does not necessarily contain an entry for every host and router on the subnet; some may have never been entered into the table, and others may have expired.

• How does ARP work:

  1. The sending host needs to obtain the MAC address of the destination given the IP address by consulting to ARP table.
  2. If the ARP table doesn’t currently have an entry for the destination,the sender constructs a special packet called an ARP packet,adapter along with an indication that the adapter should send the packet to the MAC broadcast address, namely, FF-FF-FF- FF-FF-FF.
  3. The adapter encapsulates the ARP packet in a link-layer frame, uses the broadcast address for the frame’s destination address, and transmits the frame into the subnet.
  4. The frame containing the ARP query is received by all the other adapters on the subnet, and (because of the broadcast address) each adapter passes the ARP packet within the frame up to its ARP module.Each of these ARP modules checks to see if its IP address matches the destination IP address in the ARP packet. The one with a match sends back to the querying host a response ARP packet with the desired mapping. The querying host can then update its ARP table and send its IP datagram, encapsulated in a link-layer frame whose destination MAC is that of the host or router responding to the earlier ARP query.

• Sending a Datagram off the Subnet:

  1. The sending host passes the datagram to its adapter
  2. Sending host adapter acquires the appropriate MAC address for the frame which is the address of the adapter for first hop router interface by using ARP
  3. Once the sending adapter has this MAC address, it creates a frame (containing the datagram with the target IP address of the router) and sends the frame into the Subnet . The router adapter on Subnet sees that the link-layer frame is addressed to it, and therefore passes the frame to the network layer of the router.
  4. The router now has to determine the correct interface on which the datagram is to be forwarded. This is done by consulting a forwarding table in the router.
  5. This interface then passes the datagram to its adapter, which encapsulates the datagram in a new frame and sends the frame into another Subnet. The destination MAC address is again acquired by ARP .

6.3.2 Ethernet

• Today,Ethernet mainly uses a switch-based star topology.

• switch is not only “collision-less” but is also a store-and-forward packet switch

• a switch operates only up through layer 2

• Ethernet Frame Structure

  1. Data field (46 to 1,500 bytes). This field carries the IP datagram.
  2. Destination address (6 bytes)
  3. Source address (6 bytes).
  4. Type field (2 bytes): The type field permits Ethernet to multiplex and demultiplex network-layer protocols
  5. Cyclic redundancy check (CRC) (4 bytes). the purpose of the CRC field is to allow the receiving adapter, adapter B, to detect bit errors in the frame
  6. Preamble (8 bytes). For “waking up” the receiving adapters and to synchronize their clocks to that of the sender’s clock.

• All of the Ethernet technologies provide connectionless service to the network layer. That is, there is no handshaking.

• Ethernet technologies provide an unreliable service to the network layer. Specifically, when adapter B receives a frame from adapter A, it runs the frame through a CRC check, but doesn’t send ACK or NCK. When a frame fails the CRC check, adapter B simply discards the frame.

• Ethernet Acronyms Naming Order:

  1. The first part of the acronym refers to the speed of the standard
  2. “BASE” refers to baseband Ethernet, meaning that the physical media only carries Ethernet traffic
  3. The final part of the acronym refers to the physical media itself;

6.3.2.1 Filtering And Forwarding

• Filtering is the switch function that determines whether a frame should be forwarded to some interface or should just be dropped

• Forwarding is the switch function that determines the interfaces to which a frame should be directed, and then moves the frame to those interfaces

• Switch filtering and forwarding are done with a switch table. The switch table contains entries for some, but not necessarily all, of the hosts and routers on a LAN. An entry in the switch table contains

  1. A MAC address
  2. The switch interface that leads toward that MAC address
  3. The time at which the entry was placed in the table

• In a switch-based Ethernet LAN there are no collisions because a switch coordinates its transmissions and never forwards more than one frame onto the same interface at any time. and, therefore, there is no need for a MAC protocol such as CSMA/CD.

• The switch indexes its table with the MAC address. There are three possible cases:

  1. There is no entry in the table for the address. In this case, the switch forwards copies of the frame to the output buffers preceding all interfaces except for interface it came in. In other words, if there is no entry for the destination address, the switch broadcasts the frame
  2. There is an entry in the table, associating with interface it came in. In this case, the frame is coming from a LAN segment that contains adapter with the MAC address of the requested MAC address. There being no need to forward the frame to any of the other interfaces, the switch performs the filtering function by discarding the frame.
  3. There is an entry in the table, associating the requested MAC address with interface different from the one it came in. In this case, the frame needs to be forwarded to the LAN segment attached to interface mentioned. The switch performs its forwarding function by putting the frame in an output buffer that precedes the interface.

• How the switches implement Self-Learning ability:

  1. The switch table is initially empty.
  2. For each incoming frame received on an interface, the switch stores in its table:
     1. The MAC address in the frame’s source address field
     2. The interface from which the frame arrived
     3. The current time.
  3. The switch deletes an address in the table if no frames are received with that address as the source address after some period of time (the aging time).

• We can identify several advantages of using switches, rather than broadcast links such as buses or hub-based star topologies:

  1. Elimination of collisions:The switches buffer frames and never transmit more than one frame on a segment at any one time.
  2. Heterogeneous links:the different links in the LAN can operate at different speeds and can run over different media.
  3. Management:switch also eases network management.

6.3.2.2 Switches Versus Routers

1. Switches:

• Pros:
  • Switches are plug-and-play
  • Switches can also have relatively high filtering and forwarding rates.
• Cons:
  • To prevent the cycling of broadcast frames, the active topology of a switched network is restricted to a spanning tree
  • A large switched network would require large ARP tables in the hosts and routers and would generate substantial ARP traffic and processing.
  • Switches are susceptible to broadcast storms—if one host goes haywire and transmits an endless stream of Ethernet broadcast frames, the switches will forward all of these frames, causing the entire network to collapse.

2. Routers:

• Pros:
  • Because network addressing is often hierarchical , packets do not normally cycle through routers even when the network has redundant paths.
  • Another feature of routers is that they provide firewall protection against layer-2 broadcast storms.
• Cons:
  • They are not plug-and-play—they and the hosts that connect to them need their IP addresses to be configured
  • Routers often have a larger per-packet processing time than switches, because they have to process up through the layer-3 fields.

6.3.3 Virtual Local Area Network(VLAN)

• VLAN:a switch that supports VLANs allows multiple virtual local area networks to be defined over a single physical local area network infrastructure. Hosts within a VLAN communicate with each other as if they (and no other hosts) were connected to the switch.

• VLAN trunking:In the VLAN trunking approach , a special port on each switch is configured as a trunk port to interconnect the two VLAN switches. The trunk port belongs to all VLANs, and frames sent to any VLAN are forwarded over the trunk link to the other switch.

Chapter 7 Wireless and Mobile Networks

• When we say a wireless host is“associated” with a base station, we mean that

  1. the host is within the wireless communication distance of the base station.
  2. the host uses that base station to relay data between it (the host) and the larger network.

• Hosts associated with a base station are often referred to as operating in ­infrastructure mode,since all traditional network services (e.g., address assignment and routing) are provided by the network to which a host is connected via the base station.

• In ad hoc networks, wireless hosts have no such infrastructure with which to connect. In the absence of such infrastructure, the hosts themselves must provide for services such as routing, address assignment, DNS-like name translation, and more.

• When a mobile host moves beyond the range of one base station and into the range of another, it will change its point of attachment into the larger network,a process referred to as handoff.

• At the highest level we can classify wireless networks according to two criteria:

  1. Whether a packet in the wireless network crosses exactly one wireless hop or multiple wireless hops
  2. Whether there is infrastructure such as a base station in the network
  • Single-hop, infrastructure-based. These networks have a base station that is connected to a larger wired network (e.g., the Internet). Furthermore, all communication is between this base station and a wireless host over a single wireless hop.eg:802.11 networks,4G LTE data networks.
  • Single-hop, infrastructure-less. In these networks, there is no base station that is connected to a wireless network. However, as we will see, one of the nodes in this single-hop network may coordinate the transmissions of the other nodes.eg:Bluetooth,802.11 ad hoc mode.
  • Multi-hop, infrastructure-based. In these networks, a base station is present that is wired to the larger network. However, some wireless nodes may have to relay their communication through other wireless nodes in order to communicate via the base station.eg: Wireless sensors,Wireless Mesh Networks.
  • Multi-hop, infrastructure-less. There is no base station in these networks, and nodes may have to relay messages among several other nodes in order to reach a destination. Nodes may also be mobile, with connectivity changing among nodes

• Differences between a wired link and a wireless link:

  1. Decreasing signal strength
  2. Interference from other sources
  3. Multipath propagation

• The SNR(Signal Noise Ratio), measured in dB, is twenty times the ratio of the base-10 logarithm of the amplitude of the received signal to the amplitude of the noise.

• Several physical-layer characteristics that are important in understanding higher-layer wireless communication protocols:

  1. For a given modulation scheme, the higher the SNR, the lower the bit error rate (BER).
  2. For a given SNR, a modulation technique with a higher bit transmission rate (whether in error or not) will have a higher BER.
  3. Dynamic selection of the physical-layer modulation technique can be used to adapt the modulation technique to channel conditions.

7.1 Code division multiple access (CDMA)

• Code division multiple access (CDMA) belongs to the family of channel partitioning protocols.

• In a CDMA protocol, each bit being sent is encoded by multiplying the bit by a signal (the code) that changes at a much faster rate (known as the chipping rate) than the original sequence of data bits

• How CDMA Works:

  • Let $d_i$ be the value of the data bit for the $i$th bit slot.
  • We represent a data bit with a 0 value as -1 .
  • Each bit slot is further subdivided into M mini-slots;
  • The CDMA code used by the sender consists of a sequence of M values, $c_m,m=1,2,3,…M$ ,each taking a +1 or -1 value.
  • Focus on the ith data bit, $d_i$ .For the mth mini-slot of the bit- transmission time of $d_i$ , the output of the CDMA encoder,$Z_{i,m}$, is the value of $d_i$ multiplied by the mth bit in the assigned CDMA code, $c_m$; $$ Z_{i,m} = d_i\times c_m $$
  1. With no interfering senders, the receiver would receive the encoded bits, $Z$ , and recover the original data bit, $d$ , by computing:

  $$ d_{i}=\frac{\sum_{m=1}^{M} Z_{i,m} \cdot c_{m} }{M} $$

  2. In the presence of multiple senders, sender s computes its encoded transmissions,$Z_{i,m}$, in exactly the same manner.The value received at a receiver during the $m$th mini-slot of the ith bit slot, however, is now the sum of the transmitted bits from all N senders during that mini-slot: $$ Z_{i,m}^{*} =\sum_{j=1}^{N} Z_{i,m}^{j} = \sum_{j=1}^{N} d_{i}^{j}\cdot c_{m}^{j} $$
  3. If the senders’ codes are chosen carefully(each two combination is orthogonal), each receiver can recover the data sent by a given sender out of the aggregate signal simply by using the sender’s code in exactly the same manner as in Equation : $$ d_{i}^{j} = \frac{\sum_{m=1}^{M} Z_{i,m}^{*} \cdot c_{m}^{j} }{M} $$

7.2 WiFi: 802.11 Wireless LANs

• When a network administrator installs an AP, the administrator assigns a one- or two-word Service Set Identifier (SSID) to the access point.

• Within this 85 MHz band, 802.11 defines 11 partially overlapping channels. Any two channels are non-overlapping if and only if they are separated by four or more channels. In particular, the set of channels 1, 6, and 11 is the only set of three non-overlapping channels.

• The fundamental building block of the 802.11 architecture is the basic service set (BSS). A BSS contains one or more wireless stations and a central base station, known as an access point (AP) in 802.11 parlance.

• How A Wireless Device Associates With An AP:

  1. Detect

     1. The 802.11 standard requires that an AP periodically send beacon frames, each of which includes the AP’s SSID and MAC address.
     2. Wireless devices, scan the 11 channels, seeking beacon frames

  2. Request

     1. the wireless device sends an association request frame
     2. the AP responds with an association response frame

  3. Authenticate

     • The host provides AP with some information.The AP typically communicates with an authentication server to verify these information, relaying information between the wireless device and the authentication server using a protocol such as RADIUS or DIAMETER.

  4. Assign IP The host is assigned an IP address following DHCP protocol

7.2.1 802.11 CSMA/CA Protocol

1. If initially the station senses the channel idle, it transmits its frame after a short period of time known as the Distributed Inter-frame Space (DIFS);
2. Otherwise, the station chooses a random backoff value using binary exponential backoff and counts down this value after DIFS when the channel is sensed idle. While the channel is sensed busy, the counter value remains frozen.
3. When the counter reaches zero (note that this can only occur while the channel is sensed idle), the station transmits the entire frame and then waits for an acknowledgment.
4. If an acknowledgment is received, the transmitting station knows that its frame has been correctly received at the destination station. If the station has another frame to send, it begins the CSMA/CA protocol at step 2. If the acknowledgment isn’t received, the transmitting station reenters the backoff phase in step 2, with the random value chosen from a larger interval.

• Because 802.11wireless LANs do not use collision detection, once a station begins to transmit a frame, it transmits the frame in its entirety regardless of collision.

• When the destination station receives a frame that passes the CRC, it waits a short period of time known as the Short Inter-frame Spacing (SIFS) and then sends back an acknowledgment frame.

• Why Does CSMA/CA Take Different Approach With CSMA/CD:

  1. The ability to detect collisions requires the ability to send (the station’s own ­signal) and receive (to determine whether another station is also transmitting) at the same time. Because the strength of the received signal is typically very small compared to the strength of the transmitted signal at the 802.11 adapter, it is costly to build hardware that can detect a collision.
  2. More importantly, even if the adapter could transmit and listen at the same time (and presumably abort transmission when it senses a busy channel), the adapter would still not be able to detect all collisions, due to the hidden terminal problem and fading.

• In 802.11, if the two stations sense the channel busy, they both immediately enter random backoff, hopefully choosing different backoff values. If these values are indeed different, once the channel becomes idle, one of the two stations will begin transmitting before the other, and the “losing station” will hear the “winning station’s” signal, freeze its counter, and refrain from transmitting until the winning station has completed its transmission

• Dealing With Hidden Terminals: RTS and CTS: the IEEE 802.11 protocol allows a station to use a short Request to Send (RTS) control frame and a short Clear to Send (CTS) control frame to reserve access to the channel:

  1. When a sender wants to send a DATA frame, it can first send an RTS frame to the AP, indicating the total time required to transmit the DATA frame and the acknowledgment (ACK) frame.
  2. When the AP receives the RTS frame, it responds by broadcasting a CTS frame. This CTS frame serves two purposes:
     • It gives the sender explicit permission to send.
     • Instructs the other stations not to send for the reserved duration.

  

• Although the RTS/CTS exchange can help reduce collisions, it also introduces delay and consumes channel resources. For this reason, the RTS/CTS exchange is only used (if at all) to reserve the channel for the transmission of a long DATA frame. In practice, each wireless station can set an RTS threshold such that the RTS/CTS sequence is used only when the frame is longer than the threshold.

• 802.11 frame has four address fields,each of which can hold a 6-byte MAC address, three address fields are needed for moving the network-layer datagram from a wireless station through an AP to a router interface. The fourth address field is used when APs ­forward frames to each other in ad hoc mode. Since we are only considering infrastructure networks here, let’s focus our attention on the first three address fields. The 802.11 standard defines these fields as follows:

  1. Address 1 is the MAC address of the wireless station that is to receive the frame.
  2. Address 2 is the MAC address of the station that transmits the frame
  3. Address 3 contains the MAC address of gateway router of the subnet.

• Because acknowledgments can get lost, the sending station may send multiple copies of a given frame. The sequence number field in the 802.11 frame thus serves exactly the same purpose here at the link layer as it did in the transport layer.

• The duration value is included in the frame’s duration field to request for reserve the channel for a period of time.

• 802.11 Rate Adaptation:some 802.11 implementations have a rate adaptation capability that adaptively selects the underlying physical-layer modulation technique to use based on current or recent channel characteristics.

7.3 Cellular Network

• In Cellular Network,The term cellular refers to the fact that the region covered by a cellular network is partitioned into a number of geographic coverage areas, known as cells.

• Each cell contains a base transceiver station (BTS) that transmits signals to and receives signals from the mobile stations in its cell.

7.3.1 2G

• The GSM standard for 2G cellular systems uses combined FDM/TDM (radio) for the air interface.In combined FDM/TDM systems, the channel is partitioned into a number of frequency sub-bands; within each sub-band, time is partitioned into frames and slots. Thus, for a combined FDM/TDM system, if the channel is partitioned into F sub-bands and time is partitioned into T slots, then the channel will be able to support $F\cdot T$ simultaneous calls.
• the mobile switching center (MSC) plays the central role in user authorization and accounting, call establishment and teardown, and handoff.
• The role of the base station controller (BSC) is to allocate BTS radio channels to mobile subscribers, perform paging (finding the cell in which a mobile user is resident), and perform handoff of mobile users.

7.3.2 3G

• There are two types of nodes in the 3G core network: Serving GPRS Support Nodes (SGSNs) and Gateway GPRS Support Nodes (GGSNs):

  1. An SGSN is responsible for delivering datagrams to/from the mobile nodes in the radio access network where the SGSN is attached. The SGSN interacts with the cellular voice network’s MSC for that area, providing user authorization and handoff, maintaining location (cell) information about active mobile nodes, and performing datagram forwarding between mobile nodes in the radio access network and a GGSN.
  2. The GGSN acts as a gateway, connecting multiple SGSNs into the larger Internet.

• The Radio Network Controller (RNC) typically controls several cell base transceiver stations.The RNC connects to both the circuit-switched cellular voice network via an MSC, and to the packet-switched Internet via an SGSN.

• A significant change in 3G UMTS over 2G networks is that rather than using GSM’s FDMA/TDMA scheme, UMTS uses a CDMA technique known as Direct Sequence Wideband CDMA (DS-WCDMA) within TDMA slots:TDMA slots, in turn, are available on multiple frequencies

  

7.3.3 4G

• Changes in 4G over 3G network:

  1. All-IP network architecture:the 4G architecture carries both voice and data in IP datagrams.With 4G, the last vestiges of cellular networks’ roots in the telephony have disappeared.
  2. A clear separation of the 4G data plane and 4G control plane.
  3. A clear separation between the radio access network, and the all-IP-core ­network

• The principal components of the 4G architecture are as follows:

  1. The eNodeB is the logical descendant of the 2G base station and the 3G Radio Network Controller(a.k.a Node B) and again plays a central role here. Its data-plane role is to forward datagrams between UE (over the LTE radio access ­network) and the P-GW.UE datagrams are encapsulated at the eNodeB and tunneled to the P-GW through the 4G network’s all-IP enhanced packet core (EPC).
  2. The Packet Data Network Gateway (P-GW) allocates IP addresses to the UEs and performs QoS enforcement. As a tunnel endpoint it also performs datagram encapsulation/decapsulation when forwarding a datagram to/from a UE.
  3. The Serving Gateway (S-GW) is the data-plane mobility anchor point—all UE traffic will pass through the S-GW. The S-GW also performs charging/billing functions and lawful traffic interception.
  4. The Mobility Management Entity (MME) performs connection and mobility management on behalf of the UEs resident in the cell it controls. It receives UE subscription information from the HHS.
  5. The Home Subscriber Server (HSS) contains UE information including roaming access capabilities, quality of service profiles, and authentication information.

  

• LTE Radio Access Network:LTE uses a combination of frequency division multiplexing and time division multiplexing on the downstream channel, known as orthogonal frequency division multiplexing (OFDM):In LTE, each active mobile node is allocated one or more 0.5 ms time slots in one or more of the channel frequencies.

  

7.4 Mobility

• The permanent home of a mobile node (such as a laptop or smartphone) is known as the home network
• The entity within the home network that performs the mobility management functions on behalf of the mobile node is known as the home agent
• The network in which the mobile node is currently residing is known as the foreign (or visited) network
• the entity within the foreign network that helps the mobile node with the mobility management functions discussed below is known as a foreign agent.
• A correspondent is the entity wishing to communicate with the mobile node

7.4.1 Indirect Routing

1. the correspondent simply addresses the datagram to the mobile node’s permanent address and sends the datagram into the network
2. Such datagrams are first routed, as usual, to the mobile node’s home network.
3. The datagram is forwarded to the foreign agent, using the mobile node’s Care-Of-Address(COA)
4. The datagram is forwarded from the foreign agent to the mobile node

7.4.2 Direct Routing

• We’ll identify the foreign agent in that foreign network where the mobile node was first found as the anchor ­foreign agent.
• How Direct Routing Works:
  1. A correspondent agent in the correspondent’s network querys the home agent to learn the COA of the mobile node.
  2. The correspondent agent then tunnels datagrams directly to the mobile node’s COA.
  3. When the mobile node moves to a new foreign network, the mobile node registers with the new foreign agent, and the new foreign agent provides the anchor foreign agent with the mobile node’s new COA.
  4. When the anchor foreign agent receives an encapsulated datagram for a departed mobile node, it can then re-encapsulate the datagram and forward it to the mobile node (step 5) using the new COA.

7.4.3 Mobile-IP

• The mobile IP standard consists of three main pieces:

  1. Agent discovery
  2. Registration with the home agent
  3. Indirect routing of datagrams

• Agent Discovery:A mobile IP node arriving to a new network learn the identity of the corresponding foreign or home agent.

• Agent discovery can be accomplished in one of two ways: via agent advertisement or via agent solicitation.

• With agent advertisement, the agent periodically broadcasts an ICMP message with a type field of 9 (router discovery) on all links to which it is connected. The router discovery message contains the IP address of the router (that is, the agent), thus allowing a mobile node to learn the agent’s IP address.It also contains Care-of address (COA) fields providing a list of one or more care-of addresses mobile node to choose.

• With agent solicitation, a mobile node can broadcast an agent solicitation message, which is simply an ICMP message with type value 10. An agent receiving the solicitation will unicast an agent advertisement directly to the mobile node.

• Registration with the Home Agent:

  1. Following the receipt of a foreign agent advertisement, a mobile node sends a registration message to the foreign agent carrying a COA advertised by the foreign agent, the address of the home agent (HA), the permanent address of the mobile node (MA)
  2. The foreign agent receives the registration message and records the mobile node’s permanent IP address.The foreign agent then sends a registration message to the home agent.
  3. The home agent receives the registration request , binds the mobile node’s permanent IP address with the COA; The home agent sends a mobile IP registration reply.
  4. The foreign agent receives the registration reply and then forwards it to the mobile node.Registration is complete.

7.4.4 Mobility in Cellular Networks

• How Routing Calls to a Mobile User Works In GSM:

  1. The correspondent dials the mobile user’s phone number.The call is routed from the correspondent through the PSTN to the home MSC in the mobile’s home network.
  2. The home MSC receives the call and interrogates the home location register (HLR) to determine the location of the mobile user. In the simplest case, the HLR returns the mobile station roaming number (MSRN),If HLR does not have the roaming number, it returns the address of the visitor location register (VLR) in the visited network. In this case , the home MSC will need to query the VLR to obtain the roaming number of the mobile node.
  3. Given the roaming number, the home MSC sets up the second leg of the call through the network to the MSC in the visited network. The call is completed, being routed from the correspondent to the home MSC, and from there to the visited MSC, and from there to the base station serving the mobile user.

• How the HLR obtains information about the location of the mobile user:

  1. When a mobile telephone is switched on or enters a part of a visited network that is covered by a new VLR, the mobile registers with the visited network.
  2. The visited VLR, in turn, sends a location update request message to the mobile’s HLR. This message informs the HLR of either the roaming number at which the mobile can be contacted, or the address of the VLR.
  3. As part of this exchange, the VLR also obtains subscriber information from the HLR about the mobile and determines what services (if any) should be accorded the mobile user by the visited network

• A handoff occurs when a mobile station changes its association from one base station to another during a call:

  1. The old base station (BS) informs the visited MSC that a handoff is to be performed and the BS (or possible set of BSs) to which the mobile is to be handed off.
  2. The visited MSC initiates path setup to the new BS, allocating the resources needed to carry the rerouted call, and signaling the new BS that a handoff is about to occur.
  3. The new BS allocates and activates a radio channel for use by the mobile.
  4. The new BS signals back to the visited MSC and the old BS that the visited-MSC-to-new-BS path has been established and that the mobile should be informed of the pending handoff.
  5. The mobile is informed that it should perform a handoff.
  6. The mobile and the new BS exchange one or more messages to fully activate the new channel in the new BS.
  7. The mobile sends a handoff complete message to the new BS, which is forwarded up to the visited MSC. The visited MSC then reroutes the ongoing call to the mobile via the new BS.
  8. The resources allocated along the path to the old BS are then released

  

• What happens when the mobile moves to a BS that is associated with a different MSC :

  1. GSM defines the notion of an anchor MSC. The anchor MSC is the MSC visited by the mobile when a call first begins; the anchor MSC thus remains unchanged during the call.
  2. Throughout the call’s duration, the call is routed from the home MSC to the anchor MSC, and then from the anchor MSC to the visited MSC where the mobile is currently located.

Chapter 8 Network Security

8.1 Encryption

8.1.1 Symmetric Key Encryption

Encrypted communication required that the two communicating parties share a common secret

• How Block Cipher Works:

  1. In a block cipher, the message to be encrypted is processed in blocks of k bits.
  2. Block cipher uses a function to break a k-bit block into n chunks, with each chunk consisting of k/n bits.
  3. Each k/n-bit chunk is processed by an k/n-bit to k/n-bit table
  4. Next, the n output chunks are reassembled into a new k-bit block.
  5. The positions of the k bits in the block are then scrambled (permuted) to produce a k-bit output.
  6. This output is fed back to the k-bit input, where another cycle begins.

• To avoid same ciphertext blocks originated from same cleartext blocks:The sender creates a random k-bit number r(i) for the ith block and calculates $c(i)=K_s( m(i) \oplus r(i))$,where block-cipher encryption algorithm with key S as $K_{s}$ , m(i) denote the ith plaintext block.

• In order to save overhead of sending random bits, block ciphers typically use a technique called Cipher Block Chaining (CBC):

  1. Before encrypting the message (or the stream of data), the sender generates a random k-bit string, called the Initialization Vector (IV). Denote this initialization vector by c(0). The sender sends the IV to the receiver in cleartext.
  2. For the first block, the sender calculates the exclusive-or of the first block of cleartext with the IV. It then runs the result through the block-cipher algorithm to get the corresponding ciphertext block; that is,$c(1)=K_S(m(1)\oplus c(0))$ . The sender sends the encrypted block c(1) to the receiver
  3. For the ith block, the sender generates the ith ciphertext block from $c(i)= K_S(m(i)\oplus c(i−1))$

8.1.2 Public Key Encryption

1. Suppose Alice wants to communicate with Bob.We will use the notation $K_B^+$ and $K_B^-$ to refer to Bob’s public key and private keys,respectively. Alice first fetches Bob’s public key. Alice then encrypts her message, m, to Bob using Bob’s public key and a known (for example, standardized) encryption algorithm; that is, Alice computes $K_B^+(m)$
2. Bob receives Alice’s encrypted message and uses his private key and a known (for example, standardized) decryption algorithm to decrypt Alice’s encrypted message. That is, Bob computes $m=K_B^−(K_B^+(m))$

• How Does RSA Work:

  • Generate the public and private RSA keys:

    1. Choose two large prime numbers, p and q.
    2. Compute n=pq and z=(p-1)(q-1)
    3. Choose a number, e, less than n, that has no common factors (other than 1) with z.
    4. Find a number, d, such that is exactly divisible (that is, with no ­remainder) by z. . Put another way, given e, we choose d such that: $$ e^d \ mod \ z \ = \ 1 $$
    5. The public key that Bob makes available to the world,$K_B^+$,, is the pair of numbers (n, e); his private key, $K_B^−$, is the pair of numbers (n, d).

  • Encryption:

    1. Suppose Alice wants to send Bob a bit pattern represented by the integer number m . To encode, Alice calculates ciphertext c is sent to Bob: $$ c \ = \ m^e \ mod \ n $$
    2. To decrypt the received ciphertext message, c, Bob computes $$ m=c^d \ mod \ n $$

• RSA is often used in practice in combination with symmetric key cryptography to deliver symmetric key(refered to as session key).

• How does Session Key work?

  1. Alice encrypts her message, m, with the symmetric key
  2. Encrypts the symmetric key with Bob’s public key,$K_B^{+}$
  3. Concatenates the encrypted message and the encrypted symmetric key to form a “package”
  4. Sends the package to Bob’s.
  5. He uses his private key,$K_B^−$ to obtain the symmetric key, $K_s$
  6. Bob uses the symmetric key $K_s$ to decrypt the message m

8.2 Integrity

• A cryptographic hash function is required to have the following additional property: It is computationally infeasible to find any two different messages x and y such that $H(x)=H(y)$

8.2.1 Message Authentication Code (MAC)

• Using the shared secret s, message integrity can be performed as follows:

  1. Alice creates message m, concatenates s with m to create $m+s$ , and calculates the hash $H(m+s)$ (for example with SHA-1). $H(m+s)$ is called the message authentication code (MAC)
  2. Alice then appends the MAC to the message m, creating an extended message $(m,H(m+s))$, and sends the extended message to Bob.
  3. Bob receives an extended message (m, h) and knowing s, calculates the MAC $H(m+s)$. If $H(m+s)=h$, Bob concludes that everything is fine.

• One nice feature of a MAC is that it does not require an encryption algorithm.

8.2.2 Digital Signatures

• How Digital Signatures Work?

  1. Suppose that Bob wants to digitally sign a document, m.Bob simply uses his private key,$K_B^−$,to compute $K_B^−(H(m))$,where H is a cryptographic hash function.
  2. Alice takes Bob’s public key, $K_B^{+}$,and applies it to the digital signature,That is, she computes $K_B^+(K_B^−(H(m)))$,she produces $H(m)$.
  3. Alice runs the same cryptographic hash function on the original message m and gets $H’(m)$.She compares $H(m)$ with $H’(m)$ and if they are the same the signature is valid.

• If the original document, m, is ever modified to some alternate form, $m’$ , ́the signature that Bob created for m will not be valid for $m’$,since $H(m)$ and $H(m’)$ will be different.

8.2.3 Certification

• Public key certification is certifying that a public key belongs to a specific entity.

• To verify that you have the actual public key of the entity (person, router, browser, and so on) with whom you want to communicate,Binding a public key to a Certification Authority (CA) and get a certificate.

8.2.4 End-Point Authentication

• A nonce is a number that a protocol will use only once in a lifetime

• Authentication Protocol

  1. Alice sends the message to Bob.
  2. Bob chooses a nonce, R, and sends it to Alice.
  3. Alice encrypts the nonce using Alice and Bob’s symmetric secret key,$K_{A-B}$, and sends the encrypted nonce, $K_{A-B}^{-}(R)$, back to Bob. As in protocol ap3.1, it is the fact that Alice knows and uses it to encrypt a value that lets Bob know that the message he receives was generated by Alice. The nonce is used to ensure that Alice is live.
  4. Bob decrypts the received message. If the decrypted nonce equals the nonce he sent, then Alice is authenticated.

8.3 Pretty Good Privacy (PGP)

• How Does PGP Work?

  • Sender(Alice)

    1. Alice applies a hash function, H , to her message, m, to obtain a message digest.
    2. Alice signs the digest with her private key $K_A^-$ to create a digital signature.
    3. Alice concatenates the original (unencrypted) message with the signature to create a package.
    4. Alice selects a random symmetric session key, $K_S$.
    5. Alice encrypts her package with the symmetric key
    6. Alice encrypts the symmetric key with Bob’s public key,$K_B^+$.
    7. Alice concatenates the encrypted package and the encrypted symmetric key to form a “bigger package”
    8. Alice sends the “bigger package” to Bob.

  • Receiver(Bob)

    1. When Bob receives the package, he uses his private key,$K_B^-$ to obtain the symmetric key, $K_S$.
    2. Bob uses the symmetric key $K_S$ to decrypt the package.
    3. Bob applies Alice’s public key, $K_A^+$ to the signature
    4. Bob compares the result of this operation with his own hash, H, of the message.If the two results are the same, Bob can be pretty confident that the message came from Alice and is unaltered.

8.4 SSL

• SSL can be employed by any application that runs over TCP.

• SSL has three phases: handshake, key derivation, and data transfer.

8.4.1 Handshake

1. Bob needs to establish a TCP connection with Alice
2. Bob sends Alice a list of cryptographic algorithms it supports, along with a ­client nonce.
3. Alice chooses a symmetric algorithm (for example, AES), a public key algorithm (for example, RSA with a specific key length), and a MAC algorithm. then responds with her choices, as well as a certificate and a server nonce.
4. Bob then generates a Pre Master Secret (PMS) , encrypts the PMS with Alice’s public key to create the Encrypted Master Secret (EMS), and sends the EMS to Alice.
5. Alice decrypts the EMS with her private key to get the PMS.
6. Using the same key derivation function (as specified by the SSL standard), Bob and Alice independently compute the Master Secret (MS) from the PMS and nonces. The MS is then sliced up to generate the two encryption and two MAC keys.
7. The client sends a MAC of all the handshake messages.
8. The server sends a MAC of all the handshake messages.

8.4.2 Data Transfer

1. Suppose Bob is to send data. His data is represented by data streams in TCP . SSL breaks the data stream into records.
2. Bob maintains a sequence number counter.To create the MAC, Bob inputs the record data along with the key $M_B$ and sequence number into a hash function.The result MAC is appended to each record.
3. SSL encrypts the $record \ + \ MAC$ using his session encryption key $E_B$
4. This encrypted package is then passed to TCP for transport over the Internet

8.4.2.1 SSL Record

• The Fields In A SSL Record:

  1. Type Field:The type field indicates whether the record is a handshake message or a message that contains application data.It is also used to close the SSL connection.
  2. Length Field:SSL at the receiving end uses the length field to extract the SSL records out of the incoming TCP byte stream

• SSL does not mandate that Alice and Bob use a specific symmetric key algorithm, a specific public-key algorithm, or a specific MAC.

• Truncation Attack:The intruder ends the session early with a TCP FIN.

• How To Prevent Truncation Attack:indicate in the type field whether the record serves to terminate the SSL session. (Although the SSL type is sent in the clear, it is authenticated at the receiver using the record’s MAC.)

8.5 IP security(IPsec) protocol

• The IP security protocol, more commonly known as IPsec, provides security at the network layer

• Encapsulation Security Payload (ESP) protocol:The ESP protocol provides source authentication, data integrity, and confidentiality.

• Before sending IPsec datagrams from source entity to destination entity, the source and destination entities create a network-layer logical connection. This logical connection is called a security association (SA)

• An SA is unidirectional from source to destination. If both entities want to send secure datagrams to each other, then two SAs (that is, two logical connections) need to be established, one in each direction.

• SA State Information

  • A 32-bit identifier for the SA, called the Security Parameter Index (SPI)
  • The origin interface of the SA and the destination interface of the SA.
  • The type of encryption
  • The encryption key
  • The type of integrity check
  • The authentication key

• Whenever the gateway router needs to construct an IPsec datagram for forwarding over this SA, it accesses the state information mentioned above to determine how it should authenticate and encrypt or decrypt the datagram.

• An IPsec entity stores the state information for all of its SAs in its Security Association Database (SAD).

• Along with a SAD, the IPsec entity also maintains another data structure called the Security Policy Database (SPD). The SPD indicates which SA should be used for datagrams that are to be IPsec processed;

• IPsec Datagram Structure:

• The gateway router of the sending host uses the ­following recipe to convert “original IPv4 datagram” into an IPsec datagram:

  1. Appends to the back of the original IPv4 datagram an “ESP trailer” field
  2. Encrypts the result using the algorithm and key specified by the SA
  3. Appends to the front of this encrypted datagram a field called “ESP header”; the resulting package is called the “enchilada”
  4. Creates an authentication MAC over the whole enchilada using the algorithm and key specified in the SA
  5. Appends the MAC to the back of the enchilada forming the payload
  6. Finally, creates a brand new IP header with all the classic IPv4 header fields, which it appends before the payload

• The ESP header, which is sent in the clear and consists of two fields: the SPI and the sequence number field.

• IP addresses that are in the new IP header are set to the source and destination router interfaces at the two ends of the tunnels which is the gateway router of the sending host and receiving host.

• the protocol number in this new IPv4 header field is 50, designating that this is an IPsec datagram using the ESP protocol.

8.6 Wired Equivalent Privacy (WEP)

• The IEEE 802.11 WEP protocol uses a symmetric shared key approach.
• WEP does not specify a key management algorithm.

8.6.1 WEP Authentication

• Authentication is carried out as ­follows:

1. A wireless host requests authentication by an access point.
2. The access point responds to the authentication request with a 128-byte nonce value.
3. The wireless host encrypts the nonce using the symmetric key that it shares with the access point.
4. The access point decrypts the host-encrypted nonce.
5. If the decrypted nonce matches the nonce value originally sent to the host, then the host is authenticated by the access point

8.6.2 WEP Data Encryption

• The WEP data encryption algorithm:A secret 40-bit symmetric key, $K_S$, is assumed to be known by both a host and the access point. In addition, a 24-bit Initialization Vector (IV) is appended to the 40-bit key to create a 64-bit key that will be used to encrypt a single frame:

  1. First a 4-byte CRC value is computed for the data payload

  2. The payload and the four CRC bytes are then encrypted using the RC4 stream cipher:XOR-ing the ith byte of data, $d_i$ , with the ith key $K_i^{IV}$ to produce the ith byte of ciphertext, $c_i$ : $$ ci=di \oplus k_i^{IV} $$

  3. The receiver takes the secret 40-bit symmetric key that it shares with the sender, appends the IV, and uses the resulting 64-bit key (which is identical to the key used by the sender to perform encryption) to decrypt the frame: $$ di=ci \oplus k_i^{IV} $$

8.7 Operational Security

8.7.1 Firewalls

• Firewalls can be classified in three categories: traditional packet filters, stateful filters, and application gateways.

8.7.1.1 Traditional Packet Filters

A traditional packet filter examines each datagram in isolation, determining whether the datagram should be allowed to pass or should be dropped based on package structure.

8.7.1.2 Stateful filters

Stateful filters actually track TCP connections, and use this knowledge to make ­filtering decisions:

• Create a connection table to track all ongoing TCP connections.(This is possible because the firewall can observe the beginning of a new connection by observing a three-way handshake (SYN, SYNACK, and ACK); and it can observe the end of a connection when it sees a FIN packet for the connection. )
• the stateful filter includes a new column, “check connection” in its access control list to indicate that such connection should be checked by connection table.
• When a user sends a TCP SYN segment, the user’s TCP connection gets recorded in the connection table
• On receiving a TCP packet, the firewall checks the connection table to see if this packet is part of an ongoing TCP connection, to decide whether to reject or accept the packet.

8.7.1.3 Application Gateway

An application gateway is an application-specific server through which specific application data must pass.Such a policy can be accomplished by implementing a combination of a packet filter (in a router) and a application gateway server:

• A filter configuration forces all outbound connections concernd with specific application to pass through the application gateway.
• Consider an internal user wants to use the application to connect to the outside world. The user must first set up a session with the application gateway.
• An application running in the gateway, which listens for incoming sessions, prompts the user for a user ID and password.
• When the user supplies this information, the application gateway checks to see if the user has permission .
  • If not, the connection from the internal user to the gateway is terminated by the gateway.
  • If the user has permission, then the gateway acts as a proxy server to relay messages between the user and the external host.

8.7.2 Deep packet inspection

• Deep packet inspection:look beyond the header fields and into the actual application data that the packets carry.

• A device that generates alerts when it observes potentially malicious traffic is called an intrusion detection system (IDS)

• IDS systems are broadly classified as either signature-based systems or ­anomaly-based systems:

  1. A signature-based IDS sniffs every packet passing by it, comparing each sniffed packet with the signatures in its database. If a packet (or series of packets) matches a signature in the database, the IDS generates an alert.
  2. An anomaly-based IDS creates a traffic profile as it observes traffic in normal operation. It then looks for packet streams that are statistically unusual